c++广搜模板(搜两次)

解题思路:广搜模板，搜两次就好了

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

int n,m;

char mp[55][55];

struct node{

int x;

int y;

int cnt;

}Node,t,s,k,newNode;

int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};

int gg[55][55]={0};

bool judeg(int x,int y){

if(x<0||y<0||x>=n||y>=m)

return false;

if(mp[x][y]=='1')

return false;

if(gg[x][y]!=0)

return false;

return true;

}

queue <node> q,Q;

void bfs(){

while(!q.empty()){

node top = q.front();

gg[top.x][top.y]=1;

q.pop();

if(top.x==s.x&&top.y==s.y){

s.cnt=top.cnt;

break;

}

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

int newX = top.x+dx[i];

int newY = top.y+dy[i];

if(judeg(newX,newY)==true){

Node.x=newX;

Node.y=newY;

Node.cnt=top.cnt+1;

q.push(Node);

}

}

}

}

int BFS(){

Q.push(s);

while(!Q.empty()){

node top = Q.front();

Q.pop();

gg[top.x][top.y]=1;

if(top.x==k.x&&top.y==k.y)

return top.cnt;

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

int newX = top.x+dx[i];

int newY = top.y+dy[i];

if(judeg(newX,newY)==true){

newNode.x=newX;

newNode.y=newY;

newNode.cnt=top.cnt+1;

Q.push(newNode);

}

}

}

}

int main()

{

cin>>n>>m;

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

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

cin>>mp[i][j];

if(mp[i][j]=='S'){//开始 

t.x=i;

t.y=j;

t.cnt=0;

}

if(mp[i][j]=='T'){//中转 

s.x=i;

s.y=j;

}

if(mp[i][j]=='E'){//结束 

k.x=i;

k.y=j;

}

}

}

q.push(t);

bfs();

memset(gg,0,sizeof(gg));

cout<<BFS();

return 0;

}