地图分析

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        queue<pair<int, int>> que;
        vector<vector<bool>> visited(n, vector<bool>(m, false));

        int numOfSeas = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    visited[i][j] = true;
                    que.emplace(i, j);
                } else {
                    numOfSeas++;
                }
            }
        }

        if (numOfSeas == 0 || numOfSeas == n * m) {
            return -1;
        }

        array<int, 5> moves{-1, 0, 1, 0, -1};
        int level = 0;

        while (!que.empty()) {
            level++;
            int queueSize = que.size();

            while (queueSize--) {
                auto [x, y] = que.front();
                que.pop();

                for (int i = 0; i < 4; i++) {
                    int nextX = x + moves[i], nextY = y + moves[i + 1];
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        que.emplace(nextX, nextY);
                    }
                }
            }
        }

        return level - 1;
    }
};