蒜头君回家（BFS）

蒜头君回家（BFS）"/>

蒜头君回家（BFS）

蒜头君回家
蒜头君要回家，但是他家的钥匙在他的朋友花椰妹手里，他要先从花椰妹手里取得钥匙才能回到家。
花椰妹告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”
蒜头君希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。
蒜头君生活的城市可以看做是一个n×m的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过
。蒜头君可以在城市中沿着上下左右4个方向移动，移动一个格子算做走一步。
输入格式
第一行有两个整数n，m。城市的地图是n行m列。(1≤n,m≤2000)
接下来的n行，每行m个字符，代表城市的地图。'.' 代表道路，'#' 代表障碍物，
'S' 代表蒜头君所在的位置，'T' 代表蒜头家的位置，'P'代表钥匙的位置。除了障碍物以外，
别的地方都可以通过。(题目保证蒜头君至少有一条路径可以顺利拿到钥匙并且回家)
输出格式
输出蒜头回家要走的最少步数，占一行。

样例输入
8 10
P.####.#P# 
..#..#...# 
..#T##.#.# 
.......... 
..##.##### 
.......... 
#####...## 
###....S##
样例输出
21

#include<iostream>
#include<queue>
using namespace std;
int n,m,sx,sy;
char a[1010][1010];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node 
{int x;int y;int step;bool flag;//当前状态是否拿到钥匙 node(int xx,int yy,int stepp,bool flagg){x=xx;y=yy;step=stepp;flag=flagg;}
};
bool v[1010][1010][2];//第三维表示是否拿到钥匙，0表示没有，1表示有 
queue<node>q; 
void bfs(int tx,int ty)
{v[tx][ty][0]=true;q.push(node(tx,ty,0,false));while(!q.empty()){node temp=q.front() ;q.pop() ;if(a[temp.x][temp.y]=='T'){if(temp.flag){cout<<temp.step <<endl;break;}continue;}for(int k=0;k<4;k++){int nx=temp.x +dir[k][0];int ny=temp.y +dir[k][1];if(nx<0||nx>=n||ny<0||ny>=m)continue;if(!v[nx][ny][temp.flag]&&a[nx][ny]!='#'){v[nx][ny][temp.flag]=true;if(a[nx][ny]=='P'){q.push(node(nx,ny,temp.step +1,true)); }else {q.push(node(nx,ny,temp.step +1,temp.flag)); }}}} 
} 
int main()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++)//找到起始点 {for(int j=0;j<m;j++){if(a[i][j]=='S'){sx=i;sy=j;}}}bfs(sx,sy);return 0;}