题目描述：*号是墙壁，无法通过，S是起点，T是终点，要求求S到T的最短距离

  1. 一开始没想明白怎么样是最短，这里应该是第一次遍历到的路径就是最短的，因此不需要有其他特殊操作
  2. inq数组是记录结点是否已经入过队，而不是是否被访问，因为有可能该坐标已入队但未被访问，在访问其他结点的时候多次入队，导致计算量大大增加。
  3. 这题和01小岛问题很像，模版都几乎一摸一样，可以参考一下再看一下，必须要定义的有这几个
    1. 结构体中必有x，y，可能还有其他根据题目设置的参数，然后还有个临时结点node
    2. 输入矩阵matrix、扫描矩阵inq
    3. 增量数组X、Y
    4. 矩阵大小参数m，n
    5. 判断合法xy的函数judge
    6. BFS函数
      1. 初始化起点，可以是全局变量，也可以是函数参数
      2. 将该结点押入队列，并设置inq矩阵该结点已访问
      3. 当队列不为空时，出队列，（判断是否符合退出条件，符合则返回）
      4. 使用增量矩阵开始扫描周围符合条件的结点，然后将临时结点参数更新，inq置为true，再入队列
    7. main函数中，输入矩阵初始化
      1. 如果是字符串需要使用getchar()吸收换行符，再在每一行末尾加入’\0’
    8. 根据题目要求，使用BFS得到结果
  4. 这题与小岛问题不一样的地方，第一个是这道题的输入为字符串，另外一个是小岛问题多次调用了BFS函数

代码

  1. #include<vector>
  2. #include<iostream>
  3. #include<queue>
  4. #include<algorithm>
  5. using namespace std;
  7. const int maxn = 10010;
  9. struct Node{
  10.     int x, y;
  11.     int step;
  12. }S, T, node;
  14. int n, m;
  15. int matrix[maxn][maxn];
  16. bool inq[maxn][maxn] = {false};
  17. int X[4] = {0, 0, 1, -1};
  18. int Y[4] = {1, -1, 0, 0};
  20. bool judge(int x, int y){
  21.     if(x >= n || y >= m || x < 0 || y > 0) return false;
  22.     if(matrix[x][y] == '*') return false;
  23.     if(inq[x][y] == true) return false;
  24.     return true;
  25. }
  27. int BFS(){
  28.     queue<Node> q;
  29.     q.push(S);
  30.     inq[S.x][S.y] = true;
  31.     while(!q.empty()){
  32.         Node top = q.front();
  33.         q.pop();
  34.         if(top.x == T.x && top.y == T.y) return top.step;
  35.         for(int i = 0; i < 4; i++){
  36.             int newx = top.x + X[i];
  37.             int newy = top.y + Y[i];
  38.             if(judge(newx, newy)){
  39.                 inq[newx][newy] = true;
  40.                 node.x = newx, node.y = newy, node.step = top.step + 1;
  41.                 q.push(node);
  42.             }
  43.         }
  44.     }
  45. }
  47. int main(){
  48.     scanf("%d%d", &n, &m);
  49.     for(int i = 0; i < n; i++){
  50.         getchar();
  51.         for(int j = 0; j < m; j++){
  52.             matrix[i][j] = getchar();
  53.         }
  54.         matrix[i][m+1] = '\0';
  55.     }
  56.     scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);
  57.     S.step = 0;
  58.     printf("%d",BFS);
  59.     return 0;
  60. }