链接:https://ac.nowcoder.com/acm/contest/330/C
来源:牛客网

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

在这个游戏中,它被困在了一个 n×m迷宫

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

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

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

开三维数组,vis[x][y][0/1]  然后模拟即可

有一点不是太明白,判断条件有个vis未被访问,也就是一个点最多过两次????

 #include<bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<pair<int,int>, int> Node;
const int maxn=;
char g[maxn][maxn];
int vis[maxn][maxn][];
int des[][]={-,,,-,,,,}; int bfs(pair<int,int> S,pair<int,int> T) {
memset(vis,-,sizeof(vis));
queue<Node> q;
q.push({S,});
vis[S.first][S.second][]=;
while(!q.empty()) {
Node tmp=q.front();
q.pop();
int x=tmp.first.first,y=tmp.first.second;
bool p=tmp.second;
for(int i=;i<;i++) {
int nx=x+des[i][];
int ny=y+des[i][];
if(nx<||nx>=n||ny<||ny>=m) continue;
if(~vis[nx][ny][p]) continue;
if(g[nx][ny]=='#') continue;
if(p&&g[nx][ny]=='~') continue;
if(!p&&g[nx][ny]=='w') continue;
vis[nx][ny][p]=vis[x][y][p]+;
pair<int,int> nxt={nx,ny};
if(nxt==T) return vis[nx][ny][p];
q.push({nxt,p});
}
if(g[x][y]=='@'&&vis[x][y][p^]==-) {
vis[x][y][p^]=vis[x][y][p]+;
q.push({tmp.first,p^});
}
}
return -;
} int main() {
pair<int,int> S,T;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) scanf("%s",g[i]);
for(int i=;i<n;i++) {
for(int j=;j<m;j++) {
if(g[i][j]=='S') {
S={i,j};
}
else if(g[i][j]=='T') {
T={i,j};
}
}
}
int ans=bfs(S,T);
printf("%d\n",ans);
return ;
}
04-13 23:09