[width first search] Ji Suan Ke: Suan tou Jun goes home (BFS with conditions)

 8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##

21

It is generally used to find the shortest number of steps BFS：

Conditional BFS:

Starting from S, The finish for T, When you reach the end, judge whether you have passed P（ If two conditions are met at the same time, return ）

Tag arrays use three-dimensional ：

vis[x][y][flag]

vis One more dimension indicates whether the key has been obtained .

If the terminal is reached and the state of obtaining the key is marked ,bfs end .

  You can actually walk twice at the same point , The first time was when I didn't get the key , The second time was when I got the key ?

Code ：

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
vector<string>G;
bool vis[2001][2001][2];
struct state{
	int x,y;
	int step;
	bool flag;
	state(int _x,int _y,int _step,bool _flag){
		x=_x;
		y=_y;
		step=_step;
		flag=_flag;
	}
};
 
void input(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		G.push_back(s); 
	}
	memset(vis,false,sizeof(vis));
}
void bfs(int x,int y){
	queue<state>q;
	q.push(state(x,y,0,false));
	while(!q.empty()){

		state cur=q.front();
		q.pop();
        int x=cur.x;
		int y=cur.y;
		int step=cur.step;
		bool flag=cur.flag;
		if(G[x][y]=='P'){
			flag=true;

		}
		if(G[x][y]=='T'&&flag==true){
			cout<<" They count :"<<step<<endl;
			return;
		}
	
		vis[x][y][flag]=true;

		if(x+1<n&&!vis[x+1][y][flag]&&G[x+1][y]!='#'){
			vis[x+1][y][flag]=true; 
			q.push(state(x+1,y,step+1,flag));
		}
		if(x-1>=0&&!vis[x-1][y][flag]&&G[x-1][y]!='#'){
			vis[x-1][y][flag]=true;
			q.push(state(x-1,y,step+1,flag));
		}
		if(y-1>=0&&!vis[x][y-1][flag]&&G[x][y-1]!='#'){
			vis[x][y-1][flag]=true;
			q.push(state(x,y-1,step+1,flag));
		}
		if(y+1<m&&!vis[x][y+1][flag]&&G[x][y+1]!='#'){
			vis[x][y+1][flag]=true;
			q.push(state(x,y+1,step+1,flag));
		}
	
		         		
	}
}
void output(){
	for(int i=0;i<n;i++){
		cout<<G[i]<<endl;
	}
}
void solve(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(G[i][j]=='S'){
				bfs(i,j);
				return;
			}
		}
	}
	
} 
int main(){
	input();
    solve();
}