蓝桥杯2015年第六届真题-穿越雷区 （C++代码）广搜，较为详细讲解

解题思路:

利用广搜算法来做这题，一般像这种二维数组的地图，让你走去一个地方，求最短路程都可以用深搜或者广搜，不过地图一旦大了，那么深搜就较为容易超时的，看情况来吧，地图小，深搜和广搜都可以，地图大了，还是建议广搜好一点

注意事项:

广搜的特点就是，记录起点坐标，以起点为head，遍历上下左右四个方向的地点，符合条件的地点则存储，然后tail++，不符合就不存储进来。遍历4个方向后，head++,以新的head为起点，再次遍历四个方向，符合的tail++，不符合的就下一个方向遍历，直至4个方向都尝试过了。然后又是head++.......，如此反复的一个过程

如：

3
A  +  -
+  -  +
+  -  B

可以看出答案是4对吧，A-----》（1，2）-----》（2，2）-----》（2，3）-----》B   一共四步
或者              A-----》（1，2）-----》（1，3）-----》（2，3）-----》B   一共四步

我就选第一个来说吧
一开始，在输入过程中就记录下A的坐标位置了，然后从A的四个方向遍历，符合条件就存储，tail++,不符合就不存储

h表示head,t表示tail,第四行数字表示步数

n数组xiabi下标1-m*m
第一次遍历，head(A)的位置（1，1），因为符合的只有（1，2）和（2，1）
h           t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21
0   1   1

第二次遍历，head的位置（1，2），因为符合的只有（1，3）和（2，2）
    h               t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22
0   1   1   2   2

第三次遍历，head的位置（2，1）没有符合条件的
        h           t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22
0   1   1   2   2

第四次遍历，head的位置（3，1）,因为符合的只有（2，3）           
            h          t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22  23
0   1   1   2   2   3


.........下面的步骤我就不写了，慢慢理解一下

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iomanip>
using namespace std;
//地图
char mmap[150][150];
//标技数组，就走过的地点就不再重复走了
bool book[150][150];
//方向数组，控制方向，我的顺序是右下左上
int nnext[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
//判断走不到终点的时候，就输出-1的标志变量，ff=false则说明可以走到B，ff=true则走不到B
bool ff = false;
//广搜用来存放每一步可以走的结构体数组，包含坐标，步数，和字符符号，因为+-才能走，++和--都不行，是用来存储字符比较下一步可不可以走的
typedef struct node{
 int x, y, step;
 char flag;
}node;
node n[10200];//广搜数组一般大小为m*m,因为最大是100，也就是100*100=10000，我开大一点

int main(){
 //m*m地图
 int m;
 cin >> m;
 getchar();//输入m后，吃掉回车
 int head, tail,x,y,tx,ty;
 for (int i = 1; i <= m; i++){
  for (int j = 1; j <= m; j++){
   scanf("%c", &mmap[i][j]);
   if (mmap[i][j] == 'A'){//记录起点位置，记下坐标
    x = i, y = j;
   }
   getchar();//吃掉空格和换行的回车
  }
 }
 //初始化
 head = tail = 1;//广搜实质上可以理解成一个队列，头和尾
 n[tail].x = x; n[tail].y = y; n[tail].step = 0; n[tail].flag = ' ';
 book[x][y] = 1;//标记起点位置A，说明待会广搜的话就不会再走回来起点A的位置
 tail++;
 //广搜的核心
 while (head < tail){
  for (int i = 0; i < 4; i++){
   tx = n[head].x + nnext[i][0];
   ty = n[head].y + nnext[i][1];
   //边界，超过地图边界，就不会走
   if (tx > m || tx < 1)continue;
      if(ty > m || ty < 1)continue;
   //没去过的地点，而且符合一正一负
   if (book[tx][ty] == 0 && n[head].flag != mmap[tx][ty]){
    book[tx][ty] = 1;
    n[tail].y = ty;
    n[tail].x = tx;
    n[tail].step = n[head].step+1;//步数等于上一步的步数+1
    n[tail].flag = mmap[tx][ty];
    tail++;
   }
  }
  if (n[head].flag == 'B'){
   cout << n[head].step;
   ff = true;
   break;
  }
  head++;
 }
 if (!ff)cout << -1;
 system("pause");
 return 0;
}