牛客寒假算法基础集训营4 C Applese 走迷宫

链接：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 ;

 }

巴特西

牛客寒假算法基础集训营4 C Applese 走迷宫

最新文章

热门文章