计蒜客蒜头君回家（有条件的BFS）

蒜头君要回家，但是他家的钥匙在他的朋友花椰妹手里，他要先从花椰妹手里取得钥匙才能回到家。花椰妹告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”

蒜头君希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。

蒜头君生活的城市可以看做是一个 n×m 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。蒜头君可以在城市中沿着上下左右 4 个方向移动，移动一个格子算做走一步。

输入格式

第一行有两个整数 n，m。城市的地图是 n 行 m 列。(1≤n,m≤2000)

接下来的 n 行，每行 m 个字符，代表城市的地图。'.' 代表道路，'#' 代表障碍物，'S' 代表蒜头君所在的位置，'T' 代表蒜头家的位置，'P'代表钥匙的位置。除了障碍物以外，别的地方都可以通过。(题目保证蒜头君至少有一条路径可以顺利拿到钥匙并且回家)

输出格式

输出蒜头回家要走的最少步数，占一行。

样例输入

P.####.#P#

..#..#...#

..#T##.#.#

..........

..##.#####

..........

#####...##

###....S##

样例输出

bfs 的时候标记数组多开一维度表示是否已经取得了钥匙的状态。如果到达终点并且取得钥匙的状态被标记，bfs 结束。

所以我们需要把vis数组开成三维，第三个维度来标记是否拿到钥匙，也就是同一个点其实可以走两次，第一次是没拿到钥匙的时候，第二次是拿到钥匙的时候

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 int n,m;

 char mat[][];

 bool vis[][][];

 int dir[][]={,,-,,,-,,};

 struct node{

     int x,y,step,op;

     node(){}

     node(int _x,int _y,int _step,int _op):x(_x),y(_y),step(_step),op(_op){}

 }st,key;

 void bfs(node u) {

     queue<node> q;

     q.push(u);

     vis[u.x][u.y][]=;

     while(!q.empty()) {

         node f=q.front();

         q.pop();

         printf("x=%d y=%d step=%d op=%d\n",f.x,f.y,f.step,f.op);

         if(mat[f.x][f.y]=='T'&&f.op) {

             printf("%d",f.step);

             return ;

         }

         for(int i=;i<;i++) {

             int nx=f.x+dir[i][];

             int ny=f.y+dir[i][];

             if(vis[nx][ny][f.op]||nx<||nx>=n||ny<||ny>=m||mat[nx][ny]=='#') continue;

             if(mat[nx][ny]=='P') {

                 q.push(node(nx,ny,f.step+,));

                 vis[nx][ny][]=;

             }

             else

             {

                 q.push(node(nx,ny,f.step+,f.op));

                 vis[nx][ny][f.op]=;

             }

         }

     }

 }

 int main() {

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++) {

         scanf("%s",mat[i]);

         for(int j=;j<m;j++) {

             if(mat[i][j]=='S') {

                 st.x=i;

                 st.y=j;

                 st.step=;

                 st.op=;

             }

         }

     }

     bfs(st);

     return ;

 }

巴特西

计蒜客蒜头君回家（有条件的BFS）

输入格式

输出格式

样例输入

样例输出

最新文章

热门文章

巴特西

计蒜客 蒜头君回家（有条件的BFS）

输入格式

输出格式

样例输入

样例输出

最新文章

热门文章

计蒜客蒜头君回家（有条件的BFS）