题目描述

求起点到终点的最少步数，这种是典型的BFS题，O（n）的时间复杂度。

条件：图中会有一把钥匙，一扇门，门在没有钥匙时无法通行。

做两次BFS，从起点开始，从有钥匙的地方开始。利用标记写一个BFS就可以了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include
         
           6 using namespace std; 7  8 char map[505][505]; 9 bool used[505][505][2]={
    0};10 int fx[4][2]={
    1,0,-1,0,0,1,0,-1};11 typedef struct Node{12     int x,y,k,step;13 }node;14 queue
          
            qe;15 int bfs()16 {17 while(!qe.empty())18 { node t=qe.front();19 qe.pop();20 for(int i=0;i<4;i++)21 { int key=t.k;22 int tx=t.x+fx[i][0];23 int ty=t.y+fx[i][1];24 if(map[tx][ty]=='W'||used[tx][ty][key]==1) continue;25 if(map[tx][ty]=='D'&&key==0) continue;26 if(map[tx][ty]=='K') key=1;27 used[tx][ty][key]=1;28 qe.push((node){tx,ty,key,t.step+1});29 if(map[tx][ty]=='E') return t.step+1;30 }31 }32 return -1;33 }34 int main()35 {36 int n,m,ans;37 scanf("%d%d",&n,&m);38 for(int i=0;i