BFS 2 - Shortest Path in Simple Graph

1. Knight Shortest Path

Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if knight can not reached.

int shortestPath(vector<vector<bool>>& grid, Point& source, Point& destination) {
    // BFS to get shortestPath
    // 1. 初始化
    int row = grid.size();
    if(row <= 0) return -1;
    int col = grid[0].size();
    if(col <= 0) return -1;
    vector<vector<bool>> visited(row, vector<bool>(col, false));  // 一般不要改输入的grid
    queue<Point> q;
    q.push(source);
    visited[source.x][source.y] = true;
    int moves[8][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};
    // 2. BFS
    int depth = 0;
    while(!q.empty()) {
        for(int j = q.size(); j>0; j--) {  // 求shortestPath的关键一步，遍历上次queue里所有的元素；注意j>0，没有=
            Point cur = q.front();
            q.pop();
            if(cur.x == destination.x && cur.y == destination.y) return depth;
            for(int i=0; i<8; i++) {
                int x = cur.x + moves[i][0];
                int y = cur.y + moves[i][1];
                if(x >= row || y >= col || x < 0 || y < 0 || grid[x][y] == 1 || visited[x][y]) continue;
                q.push(Point(x, y));
                visited[x][y] = true;
            }
        }
        depth++;  // depth放到最后，比如说上头，第一步就找到了，应该返回的是0
    }
    return -1;
}

2. Zombie in Matrix

Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the
number zero, one, two).
Zombies can turn the nearest people(up/down/left/right) into zombies every day,
but can not through wall.
How long will it take to turn all people into zombies? Return -1 if can not turn
all people into zombies.

Given a matrix:
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
return 2

// 新建个Point，容易表达
struct Point {
  int x;
  int y;
  Point(int xx, int yy) : x(xx), y(yy) {}
};
int zombie(vector<vector<int>>& grid) {
  int rows = grid.size();
  int cols = grid[0].size();
  queue<Point> q;
  int res = 0, people = 0;
  int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
  // 1. 先统计有多少僵尸，都放到queue里；另外，顺便记录人数
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (grid[i][j] == 1) q.push(Point(i, j));
      if (grid[i][j] == 0) people++;
    }
  }
  while (!q.empty()) {
    if (people == 0) return res;
    res++;
    // move on one step
    for (int i = q.size(); i--; i > 0) {
      Point cur = q.front();
      q.pop();
      for (int j = 0; j < 4; j++) {
        int nextx = cur.x + dir[j][0];
        int nexty = cur.y + dir[j][1];
        // 一定注意越界的问题!
        if (nextx < 0 || nextx >= rows || nexty < 0 || nexty >= cols) continue;
        if (grid[nextx][nexty] == 2 || grid[nextx][nexty] == 1) continue;
        grid[nextx][nexty] = 2;  // 感染成了僵尸，标记下，防止重复放
        q.push(Point(nextx, nexty));
        people--;
      }
    }
  }
  return -1;
}