走迷宫+钥匙和门(bfs)

xiaoxiao2021-02-28  17

就是走迷宫但会加上门,钥匙(不一定必须拿钥匙) #include<bits/stdc++.h> using namespace std; char mapp[506][506]; int b[506][506][2]; int d[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,x,y; struct nomd { int x,y,s,f; }; void bfs(int sx,int sy) { queue<nomd> q; nomd t,next; memset(b,0,sizeof(b)); t.x=sx;t.y=sy;t.s=0;t.f=0; q.push(t); b[sx][sy][0]=1; while(q.size()) { t=q.front(); q.pop(); if(mapp[t.x][t.y]=='E') { printf("%d\n",t.s); return; } for(int i=0;i<4;i++) { int nx=t.x+d[i][0],ny=t.y+d[i][1]; if(nx<0||nx>=n||ny<0||ny>=m||mapp[nx][ny]=='W') continue; next.f=t.f; if(mapp[nx][ny]=='K') next.f=1; if(mapp[nx][ny]=='D'&&next.f!=1) continue; if(b[nx][ny][next.f]==1) continue; b[nx][ny][next.f]=1; next.x=nx;next.y=ny;next.s=t.s+1; q.push(next); } } printf("-1\n"); return; } int main() { scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { scanf("%s",mapp[i]); for(int j=0;j<m;j++) { if(mapp[i][j]=='S') { x=i;y=j; } } } bfs(x,y); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2600335.html

最新回复(0)