欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【牛客 - 330C】Applese 走迷宫(bfs)

程序员文章站 2022-05-27 15:25:51
...

题干:

 

精通程序设计的 Applese 双写了一个游戏。

在这个游戏中,它被困在了一个 n×mn×m 的迷宫中,它想要逃出这个迷宫。

在迷宫中,有一些方格是水池,只有当 Applese 处于水属性的时候才可以通过;有一些方格是岩浆,只有当 Applese 是火属性的时候可以通过;有一些方格是墙壁,无论如何都无法通过;另一些格子是空地(包括起点和终点),可以*通过。
 

在一些空地上有神秘道具可以让 Applese 转换自己的属性(从水属性变为火属性或从火属性变为水属性,需要一个单位的时间)。

 

已知 Applese 在一个单位的时间内可以朝四个方向行走一格,且开始处于水属性,位于空地的道具拾取后只能在该处立即使用(或者不使用),且可以多次使用。求它走出迷宫需要的最少时间。

输入描述:

第一行两个正整数 n, m 表示迷宫的大小。
接下来 n 行,每行长度为 m 的字符串。描述地图。
其中 'S' 表示起点,'T' 表示终点,'.' 表示空地,'w'表示岩浆,'~'表示水池,'@' 表示道具,'#'表示障碍。
保证地图中的起点和终点只有一个,道具都位于空地。

输出描述:

输出一个整数,表示 Applese 走出迷宫的最短时间。特别地,如果 Applese 走不出迷宫,输出 "-1"。

示例1

输入

复制

5 5
[email protected]
.S#..
~w#..
.w..~
@w.~T

输出

复制

18

备注:

1≤n,m≤100

 

解题报告:

   直接bfs就行了,,注意要用pq,,不能直接用队列、、之前在这里就栽过坑。。。还有啊,,根据样例,起点是可以重复走的、、(代码虽然挺好看但是还是比较冗长的、、)

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
char maze[505][505];
bool vis[505][505][2];//0:水 1:火
int nx[4] = {0,1,0,-1};
int ny[4] = {1,0,-1,0};
struct Node {
	int x,y;
	int t;
	bool q;
	Node(){}
	Node(int x,int y,int t,bool q):x(x),y(y),t(t),q(q){}
	bool operator<(const Node b) const{
		return t > b.t;
	}
};
int n,m;
int edx,edy,stx,sty;
bool ok(int x,int y) {
	if(x >=1 && x <= n && y >= 1 && y <= m) return 1;
	else return 0 ;
}
int bfs(int stx,int sty) {
	priority_queue<Node> q;
	q.push(Node(stx,sty,0,0));
	vis[stx][sty][0] = 1;
	while(q.size()) {
		Node cur = q.top();q.pop();
		if(cur.x == edx && cur.y == edy) return cur.t;
		for(int k = 0; k<4; k++) {
			int tx = cur.x + nx[k];
			int ty = cur.y + ny[k];
			if(!ok(tx,ty)) continue;
			if(maze[tx][ty] == 'T') return cur.t+1;
			if(maze[tx][ty] == '.') {
				if(vis[tx][ty][cur.q] == 0) 
					vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));
			}
			if(maze[tx][ty] == 'w') {
				if(vis[tx][ty][cur.q] == 0 && cur.q == 1) 
					vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));
			}
			if(maze[tx][ty] == '~') {
				if(vis[tx][ty][cur.q] == 0 && cur.q == 0) 
					vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));
			}
			if(maze[tx][ty] == '#') continue;
			if(maze[tx][ty] == '@') {
				if(vis[tx][ty][cur.q] == 0) 
					vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));
				if(vis[tx][ty][!cur.q] == 0) 
					vis[tx][ty][!cur.q] = 1, q.push(Node(tx,ty,cur.t+2,!cur.q));
			}
		}
	}
	return -1;
} 
int main()
{
	cin>>n>>m;
	for(int i = 1; i<=n; i++) {
		scanf("%s",maze[i]+1);
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=m; j++) {
			if(maze[i][j] == 'S') stx = i, sty = j,maze[i][j] = '.';
			if(maze[i][j] == 'T') edx = i, edy = j;
		}
	}
	int ans = bfs(stx,sty);
	printf("%d\n",ans);
	return 0 ;
 }