做题笔记：[LeetCode 1162. 地图分析

LeetCode 1162. 地图分析 做题笔记

思路：

对于这道题，我第一反应是用 bfs 暴力搜（在TLE的边缘试探），看了一下官方的题解，基于变种的 dijkstra 来做的思路挺好的，就记录一下自己的实现过程。

题目需要求海洋中到陆地的最远距离（距离的定义是海洋到最近陆地的距离，看题吧我也就这么解释了）， dijkstra 可用来求单源最短路径。

我们以所有陆地作为源点，利用 dijkstra 去更新各个海洋到源点的距离，当更新结束时，我们便得到了各个海洋到最近的陆地的距离，我们从这些距离中找到最大的距离即可。

注意：dijkstra 的距离在初始化时设为 INF ，故在最后输出时还需要判断最大距离是否为 INF，若为则说明全是海洋，输出 -1 。

代码实现

#define INF 0x3f3f3f3f

struct pos{
    int x, y, cost;
    bool operator<(const pos &b) const {
        return cost > b.cost;
    }
};

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int row = grid.size();
        if(row == 0)
            return -1;
        int col = grid[0].size();

        int dist[row][col];
        memset(dist, INF, sizeof(dist));

        priority_queue<pos> que;
        for(int i = 0; i < row; ++i) {
            for(int j = 0; j < col; ++j) {
                if(grid[i][j] == 1) {
                    // 将所有陆地设为原点
                    dist[i][j] = 0;
                    que.push({i, j, 0});
                }
            }
        }

        while(!que.empty()) {
            pos p = que.top();
            que.pop();

            if(p.cost > dist[p.x][p.y])
                continue;

            for(int i = 0; i < 4; ++i) {
                int x = p.x + op[i][0], y = p.y + op[i][1];

                if(0 <= x && x < row && 0 <= y && y < col) {
                    if(dist[x][y] > p.cost + 1) {
                        dist[x][y] = p.cost + 1;
                        que.push({x, y, dist[x][y]});
                    }
                } 
            }
        }

        int ans = -1;
        for(int i = 0; i < row; ++i) {
            for(int j = 0; j < col; ++j) {
                if(grid[i][j] == 0)
                    ans = max(ans, dist[i][j]);
            }
        }

        return ans == INF ? -1 : ans;
    }

private:
    const int op[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
};