题解 | 走格子

#include <array>
#include <queue>
#include <vector>
class Flood {
  public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        vector<vector<bool>>vis(n, vector<bool>(m, false));
        int step = 0;
        queue<pair<int, int>> pos;
        pos.push({0, 0});
        array<int, 4> dx = {1, 0, -1, 0};
        array<int, 4>dy = {0, 1, 0, -1};

        while (!pos.empty()) {
            int sz = pos.size();
            while (sz--) {
                auto [x, y] = pos.front();
                if (x == n - 1 && y == m - 1) return step;
                pos.pop();
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0 &&
                            !vis[nx][ny]) {
                        pos.push({nx, ny});
                        vis[nx][ny] = true;
                    }
                }
            }
            ++step;

        }
        return -1;
    }
};