本文主要是介绍68-蒜头君回家，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
蒜头君要回家，但是他家的钥匙在他的朋友花椰妹手里，他要先从花椰妹手里取得钥匙才能回到家。花椰妹告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”
蒜头君希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。
蒜头君生活的城市可以看做是一个 n×m 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。蒜头君可以在城市中沿着上下左右 4 个方向移动，移动一个格子算做走一步。
输入格式
第一行有两个整数 n，m。城市的地图是 n 行 m 列。(1≤n,m≤2000)
接下来的 n 行，每行 m 个字符，代表城市的地图。'.' 代表道路，'#' 代表障碍物，'S' 代表蒜头君所在的位置，'T' 代表蒜头家的位置，'P'代表钥匙的位置。除了障碍物以外，别的地方都可以通过。(题目保证蒜头君至少有一条路径可以顺利拿到钥匙并且回家)
输出格式
输出蒜头回家要走的最少步数，占一行。
样例输入
8 10 P.####.#P# ..#..#...# ..#T##.#.# .......... ..##.##### .......... #####...## ###....S##
样例输出
21
解题说明：这里我们并不是先搜索所有钥匙，再从每个每个钥匙出发找终点，这样肯定会超时。
我们就搜一次，真的就一次！搜索的过程中，找到钥匙的，其后面走过的坐标都记标志，标志说明我已经有钥匙了，没有标识，则经过终点也继续搜。记一个flag不行，不同的路径在搜，可能其中一条找到钥匙了，你变了flag，另外的没有钥匙的到了终点判断到了，就错了。
标志的问题，多加一维，已经有钥匙了有没走过，和没有钥匙的走没走过。
代码解析：
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxl 2010
using namespace std;
int n,m;
int a[maxl][maxl],vist[maxl][maxl][2];
int cg[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct point{ int x;int y;int foot;int flag; point(int xx,int yy,int fot,int f){ x=xx;y=yy;foot=fot;flag=f; }
};
int bfs(int x,int y){ queue<point>q; q.push(point(x,y,0,0)); vist[x][y][0]=1; while(!q.empty()){ point po=q.front(); q.pop(); for(int i=0;i<4;i++){ int tx=po.x+cg[i][0]; int ty=po.y+cg[i][1]; if(a[tx][ty]!='#'&&!vist[tx][ty][po.flag]&&tx>0&&tx<=n&&ty>0&&ty<=m){ vist[tx][ty][po.flag]=1; if(a[tx][ty]=='P'){ q.push(point(tx,ty,po.foot+1,1)); } else if(a[tx][ty]=='T'&&po.flag){ return po.foot+1; } else q.push(point(tx,ty,po.foot+1,po.flag)); } } }
}
int main(){ scanf("%d%d",&n,&m); memset(vist,0,sizeof(vist)); int bx,by; for(int i=1;i<=n;i++){ getchar(); for(int j=1;j<=m;j++){ scanf("%c",&a[i][j]); if(a[i][j]=='S'){ bx=i;by=j; } } } printf("%d\n",bfs(bx,by)); return 0;
} 这篇关于68-蒜头君回家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
