[数据结构与算法]LeetCode 1765:地图中的最高点

LeetCode 1765:地图中的最高点

原题地址

基本思路

多源BFS，将水域装入队列中，接着取出队头元素，将其周围未标记高度的区块设置为该区块的高度+1，并装入队尾。反复操作直到队列为空。时间复杂度为O(mn)，空间复杂度为O(mn)。

错误思路

构思出了扩散法，即每次将一些元素扩散到四周的元素。这样可以得到正确答案，但没想到BFS，没有使用队列，每次都通过遍历地图矩阵的方式找到可操作的元素，使得复杂度达到了O(mn*maxHeight)，导致最后超时。因此图类问题还是应该从图的基本算法出发思考。

代码

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

        vector<vector<int>> matrix(isWater.size(), vector<int>(isWater[0].size(), -1));
        
        std::queue<pair<int, int>> q;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size(); j++)
            {
                if(isWater[i][j] == 1)
                {
                    matrix[i][j] = 0;
                    q.push({i,j});
                }            
            }
        }
        while(!q.empty())
        {
            auto node = q.front();
            q.pop();
            int i=node.first;
            int j=node.second;
            int h = matrix[i][j];
            if(i>0 && matrix[i-1][j]<0)
            {
                matrix[i-1][j] = h+1;
                q.push({i-1,j});
            }                    
            if(j<matrix[0].size()-1  && matrix[i][j+1]<0)
            {
                matrix[i][j+1] = h+1;
                q.push({i,j+1});
            }                 
            if(i<matrix.size()-1 && matrix[i+1][j]<0)
            {
                matrix[i+1][j] = h+1;
                q.push({i+1,j});
            }                    
            if(j>0 && matrix[i][j-1]<0)
            {
                matrix[i][j-1] = h+1;
                q.push({i,j-1});
            }    
        }

        return matrix;
    }
};