题解 | 走迷宫

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  最短路先想bfs
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#define pre(i,j,k) for (int i = j; i < k; i++)
#define pi pair<int,int>
using namespace std;
array<int, 4> dx{0,0,1,-1}, dy{1,-1,0,0};
int main() {
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<vector<char>> a(n, vector<char>(m));
  vector<vector<int>> len(n,vector<int>(m, -1));
  bool flag = 1;
  int qx, qy, fx, fy;
  cin >> qx >> qy >> fx >> fy;
  len[qx - 1][qy - 1] = 0;
  if (qx == fx && qy == fy){
    cout << 0;
    return 0;
  }
  pre(i,0,n)
  pre(j,0,m)
  cin >> a[i][j];
  queue<pi> q;
  q.push(pi(qx - 1, qy - 1));//----------起点入队
  while(!q.empty()){//---------如果队列不为空
    pi np = q.front();
    q.pop();
    pre(i,0,4){
      int nx = np.first + dx[i], ny = np.second + dy[i];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;//-------各种检测
      if (a[nx][ny] == '*') continue;
      else if (len[nx][ny] != -1) continue;
      q.push(pi(nx, ny));
      len[nx][ny] = len[np.first][np.second] + 1;//---------跟新起点到这个点的最短路
      if (nx == fx - 1 && ny == fy - 1){//---------如果找到了终点
        flag = 0;
        break;
      }      
    }
  }
  if (flag) {//--------如果从起点能走到的点都遍历完了还没找到终点
    cout << -1;
  }
  return 0;
}
// 64 位输出请用 printf("%lld")