摘要:题目链接这道题感觉是那道的简化版,思路都是一样的。是把所有的点都先放到里面,然后一起遍历。这种写法的好处是保证了每个点都只被放进一次,不会重复遍历。保证了时间复杂是。可以不写成层次遍历的形式,直接,的程序
Walls and Gates
题目链接:https://leetcode.com/problems...
这道题感觉是那道“Shortest Distance from All Buildings”的简化版,思路都是一样的。链接:https://segmentfault.com/a/11...
public class Solution { public void wallsAndGates(int[][] rooms) { /* bfs for each gates, room[i][j] = distance from (i, j) to gate * update room[i][j] each time * bfs: 1. qand level * 2. go over current level * if (x, y) is in matrix && empty && room[x][y] > level * - room[x][y] = level * - q.offer(x, y) */ for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == 0) bfs(rooms, i, j); } } } int[] dx = new int[] {-1, 1, 0, 0}; int[] dy = new int[] {0, 0, -1, 1}; private void bfs(int[][] rooms, int x, int y) { Queue q = new LinkedList(); q.offer(new int[] {x, y}); int level = 0; // 1. bfs loop use a queue while(!q.isEmpty()) { level++; // 2. go over current level for(int j = q.size(); j > 0; j--) { int[] cur = q.poll(); // 4 directions for(int i = 0; i < 4; i++) { int nx = cur[0] + dx[i], ny = cur[1] + dy[i]; // if (x, y) is in matrix && empty && room[x][y] > level if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > level) { rooms[nx][ny] = level; q.offer(new int[] {nx, ny}); } } } } } }
看到discussion里面bfs还有一种写法。是把所有gates的点都先放到q里面,然后一起遍历。这种写法的好处是:保证了每个点都只被放进q一次,不会重复遍历。保证了时间复杂是O(MN), M = rooms.length, N = rooms[0].length。
public class Solution { public void wallsAndGates(int[][] rooms) { /* bfs */ Queueq = new LinkedList(); for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == 0) q.offer(new int[] {i, j}); } } bfs(rooms, q); } int[] dx = new int[] {-1, 1, 0, 0}; int[] dy = new int[] {0, 0, -1, 1}; private void bfs(int[][] rooms, Queue q) { int level = 0; while(!q.isEmpty()) { level++; for(int j = q.size(); j > 0; j--) { int[] cur = q.poll(); // 4 directions for(int i = 0; i < 4; i++) { int nx = cur[0] + dx[i], ny = cur[1] + dy[i]; if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > level) { rooms[nx][ny] = level; q.offer(new int[] {nx, ny}); } } } } } }
可以不写成层次遍历的形式,直接bfs,level = poll + 1:
public class Solution { public void wallsAndGates(int[][] rooms) { /* bfs */ Queueq = new LinkedList(); for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == 0) q.offer(new int[] {i, j}); } } bfs(rooms, q); } int[] dx = new int[] {-1, 1, 0, 0}; int[] dy = new int[] {0, 0, -1, 1}; private void bfs(int[][] rooms, Queue q) { while(!q.isEmpty()) { int[] cur = q.poll(); int x = cur[0], y = cur[1]; // 4 directions for(int i = 0; i < 4; i++) { int nx = cur[0] + dx[i], ny = cur[1] + dy[i]; if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > rooms[x][y] + 1) { rooms[nx][ny] = rooms[x][y] + 1; q.offer(new int[] {nx, ny}); } } } } }
dfs的程序:
public class Solution { public void wallsAndGates(int[][] rooms) { /* dfs */ for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == 0) dfs(rooms, i, j, 0); } } } int[] dx = new int[] {-1, 1, 0, 0}; int[] dy = new int[] {0, 0, -1, 1}; private void dfs(int[][] rooms, int x, int y, int depth) { for(int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx >= 0 && nx < rooms.length && ny >= 0 && ny < rooms[0].length && rooms[nx][ny] > depth + 1) { rooms[nx][ny] = depth + 1; dfs(rooms, nx, ny, depth + 1); } } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66555.html
摘要:广度优先搜索复杂度时间空间思路实际上就是找每个房间到最近的门的距离,我们从每个门开始,广度优先搜索并记录层数就行了。这题要注意剪枝,如果下一步是门或者下一步是墙或者下一步已经访问过了,就不要加入队列中。 Walls and Gates You are given a m x n 2D grid initialized with these three possible values....
摘要:题目解答每一次加入进来的结点,都时当前位置可到达的最短距离。 题目: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...
Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...
摘要:本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言迷宫对于大家都不会陌生那么迷宫是怎么生成已经迷宫要如何找到正确的路径呢用代码又怎么实现带着这些问题我们继续往下看并查集朋友圈有一种算法就做并查集什么意思呢比如现在有零 本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...
阅读 1010·2021-11-22 13:52
阅读 924·2019-08-30 15:44
阅读 570·2019-08-30 15:43
阅读 2424·2019-08-30 12:52
阅读 3473·2019-08-29 16:16
阅读 637·2019-08-29 13:05
阅读 2943·2019-08-26 18:36
阅读 1974·2019-08-26 13:46