首页 > 代码库 > 286. Walls and Gates
286. Walls and Gates
You are given a m x n 2D grid initialized with these three possible values.
-1
- A wall or an obstacle.0
- A gate.INF
- Infinity means an empty room. We use the value231 - 1 = 2147483647
to representINF
as you may assume that the distance to a gate is less than2147483647
.
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
此题解法与
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。