首页 > itarticle > bfs 2 – shortest path in simple graph

bfs 2 – shortest path in simple graph

admin 11月 11, 2020 0

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) {
  int res = 0;
  int rows = grid.size(), cols = grid[0].size();
  if (source.x == destination.x && source.y == destination.y) return 0;
  int moves[8][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};
  queue<Point> q;
  q.push(source);
  grid[source.x][source.y] = 1;
  while (!q.empty()) {
    res++;
    for (int i = q.size(); i > 0; i--) {
      Point cur = q.front();
      q.pop();
      for (int j = 0; j < 8; j++) {
        int destx = cur.x + moves[j][0], desty = cur.y + moves[j][1];
        if (destx >= rows || destx < 0 || desty >= cols || desty < 0) continue;
        if (grid[destx][desty] == 1) continue;
        if (destx == destination.x && desty == destination.y) return res;
        q.push(Point(destx, desty));
        grid[destx][desty] = 1;  // 标记，防止死循环，不能重复放
      }
    }
  }
  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

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};
  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;  // 不能重放2次
        q.push(Point(nextx, nexty));
        people--;
      }
    }
  }
  return -1;
}