【牛客 - 330C】Applese 走迷宫（bfs）

题干：

 

精通程序设计的 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 ;
 }