本文共 1583 字，大约阅读时间需要 5 分钟。
bfs
注意事项
#include #include #include #include using namespace std;int n,m;char a[302][302];char usual[302][302];char special[302][302];int dx[4] = {0,1,0,-1};int dy[4] = {1,0,-1,0};struct qwq { int my_x1,my_x2,my_y1,my_y2; int flag;};map cs;int be_x,be_y;struct Pos { int x,y,step;};queue bfs;int main() { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>a[i][j]; special[i][j]=a[i][j]; usual[i][j]=a[i][j]; if(a[i][j]>='A'&&a[i][j]<='Z') { if(cs[a[i][j]].flag==0) { cs[a[i][j]].my_x1=i; cs[a[i][j]].my_y1=j; cs[a[i][j]].flag++; } else { cs[a[i][j]].my_x2=i; cs[a[i][j]].my_y2=j; cs[a[i][j]].flag++; } special[i][j]=a[i][j]; } else if(a[i][j]=='@') { be_x=i; be_y=j; } } } bfs.push({be_x,be_y,0}); while(!bfs.empty()) { Pos head = bfs.front(); for(int i = 0; i < 4; i++) { int tx = head.x+dx[i], ty = head.y+dy[i]; if(a[tx][ty]=='=') { cout< < ='A'&&a[tx][ty]<='Z' && special[tx][ty]!='#' ) { if(cs[a[tx][ty]].flag==1) { special[tx][ty]='#'; bfs.push({tx,ty,head.step+1}); continue; } special[tx][ty]='#'; char flag2=a[tx][ty]; if(cs[flag2].my_x1==tx && cs[flag2].my_y1 == ty) { tx=cs[flag2].my_x2; ty=cs[flag2].my_y2; } else { tx=cs[flag2].my_x1; ty=cs[flag2].my_y1; } bfs.push({tx,ty,head.step+1}); } else if(a[tx][ty]=='.' && usual[tx][ty]=='.') { usual[tx][ty]='#'; bfs.push({tx,ty,head.step+1}); } } bfs.pop(); } return 0;}
转载于:https://www.cnblogs.com/ainiyuling/p/11188478.html