使用int visit[505][505][2];来实现分类讨论(当拿到钥匙之后就清零此路径的检查数组)
我的方法就是自己想的一个思路:
将分类讨论简化了 争对与这道题的简化 可能其他题就不行了
我认为首先肯定需要检查是否走过(visit数组),而且需要bfs的框架
分析:
如果不设置检查机制肯定不行(如果压根就不能出去那么就会一直循环) 如果老方法设置也不行(比如必须要钥匙,但钥匙在出口反方向那就不能返回了)
我们分析会知道如果拿到钥匙,我们把检查是否走过全部清零不就可以找到出口了嘛!(但这会影响不拿钥匙的检查呀) 所以我就用两个检查数组解决(一个是不走钥匙这条路 一个是拿到钥匙之后)
#include <iostream> #include <queue> using namespace std; char place[505][505]; int visit[505][505][2]; struct Step{ int x,y,steps; bool has_key;//是否有钥匙 //构造函数 Step(int xx,int yy,int ss,bool hh):x(xx),y(yy),steps(ss),has_key(hh){} }; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; queue<Step> q; int main() { int H,W,x,y; cin>>H>>W; for(int i=0;i<H;i++) for(int j=0;j<W;j++){ cin>>place[i][j]; if(place[i][j]=='S'){ x=i;y=j; } } q.push(Step(x,y,0,false)); visit[x][y][0]=1; while(!q.empty()){ Step s=q.front(); int step=s.steps+1; if(place[s.x][s.y]=='E'){ cout<<s.steps<<endl; return 0; } for(int i=0;i<4;i++){ int tox=s.x+dx[i]; int toy=s.y+dy[i]; if(place[tox][toy]=='W')continue; if(s.has_key){ if(visit[tox][toy][1]==1)continue; }else{ if(visit[tox][toy][0]==1)continue; } if(place[tox][toy]=='D'){ if(s.has_key){ q.push(Step(tox,toy,step,s.has_key)); visit[tox][toy][1]=1; } continue; } if(place[tox][toy]=='K'){ q.push(Step(tox,toy,step,true)); visit[tox][toy][0]=1; visit[tox][toy][1]=1; continue; } q.push(Step(tox,toy,step,s.has_key)); if(s.has_key){ visit[tox][toy][1]=1; }else{ visit[tox][toy][0]=1; } } q.pop(); } cout<<"-1"<<endl; return 0; }