lintcode 663. 墙和门迷宫问题bfs

太过爱你忘了你带给我的痛 2023-05-22 06:34 17阅读 0赞

您将获得一个使用这三个可能值初始化的 m×n 2D 网格。  
\-1 - 墙壁或障碍物。  
0 - 门。  
INF - Infinity是一个空房间。我们使用值 2 ^ 31 - 1 = 2147483647 来表示INF，您可以假设到门的距离小于 2147483647。  
在代表每个空房间的网格中填入到距离最近门的距离。如果不可能到达门口，则应填入 INF。

样例
    样例1
    
    输入：
    [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
    输出：
    [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
    解释：
    2D网络为：
    INF  -1  0  INF
    INF INF INF  -1
    INF  -1 INF  -1
      0  -1 INF INF
    答案为：
      3  -1   0   1
      2   2   1  -1
      1  -1   2  -1
      0  -1   3   4
    样例2
    
    输入：
    [[0,-1],[2147483647,2147483647]]
    输出：
    [[0,-1],[1,2]]

思路：  
1、找到所有门所在的位置。  
2、从门的地方开始进行广度搜索，门刚好是0，所以找到的每个房间值应该修改为上一个房间值+1  
3、要注意一个房间被多次搜索时，一定是第一次被搜到的值最小，所以，当一个房间值不是2147483647时，就没有必要再去修改了，这样也避免了陷入死循环。

class Solution {
        
    public:
        /**
         * @param rooms: m x n 2D grid
         * @return: nothing
         */
        struct node
        {
        
            int x;
            int y;
          //  int step;
        };
        void wallsAndGates(vector<vector<int>> &rooms) {
        
            // write your code here
            queue<node> q;
            int n=rooms.size();
            int m=rooms[0].size();
            for (int i = 0; i < n; i++) {
        //找到所有门的位置
                for(int j = 0; j < m;j++)
                {
        
                    if(rooms[i][j]==0)
                    {
        
                        node door;
                        door.x=i;
                        door.y=j;
                    //    door.step=0;
                        q.push(door);
                    }
                }
            }
            int dx[4]={
        0,1,0,-1};
            int dy[4]={
        1,0,-1,0};
            while(!q.empty())
            {
        //bfs找到每个房间到门的最小距离
                node front=q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
        
                    int x=front.x+dx[i];
                    int y=front.y+dy[i];
                    if(x<0||y<0||x>=n||y>=m||rooms[x][y]==-1)continue;
                    if(rooms[x][y]==2147483647)
                    {
        
                        rooms[x][y]=rooms[front.x][front.y]+1;
                        node New;
                        New.x=x;
                        New.y=y;
                        q.push(New);
                    }
                }
            }
        }
    };