首页 > 代码库 > 286. Walls and Gates

286. Walls and Gates

2024-08-13 01:20:17   218人阅读

You are given a m x n 2D grid initialized with these three possible values.

  1. -1 - A wall or an obstacle.
  2. 0 - A gate.
  3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INFINF INF INF  -1INF  -1 INF  -1  0  -1 INF INF

 

After running your function, the 2D grid should be:

  3  -1   0   1  2   2   1  -1  1  -1   2  -1  0  -1   3   4


此题解法与 (M) Number of Islands 类似。
 
public void WallsAndGates(int[,] rooms) {        int row = rooms.GetLength(0);        int col = rooms.GetLength(1);        for(int i = 0;i< row;i++)        {            for(int j =0;j< col;j++)            {                if(rooms[i,j] == 0)                {                    DFS(rooms, i+1,j,row,col, 0 );                    DFS(rooms, i-1,j,row,col, 0 );                    DFS(rooms, i,j-1,row,col, 0 );                    DFS(rooms, i,j+1,row,col, 0 );                }            }        }        return;    }        private void DFS(int[,] rooms, int x,int y, int row,int col,int sentinel)    {        if(x<0 || x>= row) return;        if(y<0 || y>= col) return;        if(rooms[x,y] <= 0) return;         if(rooms[x,y] < sentinel+1) return;        rooms[x,y] =sentinel+1;        DFS(rooms, x+1,y,row,col, rooms[x,y] );        DFS(rooms, x-1,y,row,col, rooms[x,y] );        DFS(rooms, x,y-1,row,col, rooms[x,y] );        DFS(rooms, x,y+1,row,col, rooms[x,y] );    }

 

286. Walls and Gates


联系
我们