题目：

1242

1 //这是一个比较标准的bfs，没有经过任何优化，但是思路比较清晰，容易看懂。  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 using namespace std;  6 //node结构体  7 typedef struct    8 {  9     int x; 10     int y; 11     int len; 12 }node; 13 //全局变量定义 14 #define M 202 15 char Map[M][M];//地图 16 int mask[M][M];//访问标志 17 queue
        
          q;//队列，只在bfs中用到 18 int bx,by,ex,ey,w,h;//起点、终点、宽、高 19 int step[4][2] = {
   //四个方向 20     //0-up 21     0,-1, 22     //1-right 23     1,0, 24     //2-down 25     0,1, 26     //3-left 27     -1,0 28 }; 29  30 void readMap(int m,int n);//读取地图 31 void bfs();//bfs 32 int tryXY(int x,int y);//尝试x、y点 33  34 void main() 35 { 36     while (scanf("%d %d",&h,&w)==2) 37     { 38         readMap(h,w); 39         bfs(); 40         cout<
         
          <
          
           >Map[i][j]; 52 mask[i][j] = -1;//标志为未访问 53 if (Map[i][j] == 'r') 54 { //friend为起点，且化为road 55 Map[i][j] = '.'; 56 bx = i; by = j; 57 } 58 if (Map[i][j] == 'a') 59 { //angel为终点，且化为road 60 Map[i][j] = '.'; 61 ex = i; ey = j; 62 } 63 } 64 } 65 } 66 67 void bfs() 68 { 69 node n,m;//m为队头，n为m衍生的测试点 70 int i,ret; 71 //起点 72 m.x = bx; 73 m.y = by; 74 m.len = 0;//len 75 mask[bx][by] = 0;//ask 76 q.push(m);//push 77 //处理 78 while (q.size()) 79 { 80 //get front 81 m = q.front(); 82 q.pop(); 83 //test node m 84 for (i=0 ; i<4 ; i++) 85 { 86 n.x = m.x+step[i][0]; n.y = m.y+step[i][1]; n.len = m.len+1; 87 ret = tryXY(n.x,n.y); 88 switch(ret) 89 { 90 case -1:// 91 break; 92 case 0: 93 case 1: 94 n.len += ret; 95 //如果为访问，保存花销；如果已经访问，保存花销最少。 96 if (mask[n.x][n.y] == -1 || n.len
           
            =0 && x
            
             =0 && y