题干：
精通程序设计的 Applese 双写了一个游戏。
在这个游戏中，它被困在了一个 n×mn×m 的迷宫中，它想要逃出这个迷宫。
在迷宫中，有一些方格是水池，只有当 Applese 处于水属性的时候才可以通过；有一些方格是岩浆，只有当 Applese 是火属性的时候可以通过；有一些方格是墙壁，无论如何都无法通过；另一些格子是空地（包括起点和终点），可以自由通过。
在一些空地上有神秘道具可以让 Applese 转换自己的属性（从水属性变为火属性或从火属性变为水属性，需要一个单位的时间）。
已知 Applese 在一个单位的时间内可以朝四个方向行走一格，且开始处于水属性，位于空地的道具拾取后只能在该处立即使用（或者不使用），且可以多次使用。求它走出迷宫需要的最少时间。
输入描述:
第一行两个正整数 n, m 表示迷宫的大小。 接下来 n 行，每行长度为 m 的字符串。描述地图。 其中 'S' 表示起点，'T' 表示终点，'.' 表示空地，'w'表示岩浆，'~'表示水池，'@' 表示道具，'#'表示障碍。 保证地图中的起点和终点只有一个，道具都位于空地。
输出描述:
输出一个整数，表示 Applese 走出迷宫的最短时间。特别地，如果 Applese 走不出迷宫，输出 "-1"。
示例1
输入
5 5 .w@.. .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 ;
}
京公网安备 11010502036488号