BFS迷宫寻路 286. Walls and Gates
先把标准答案粘过来:
我参考了标准答案的两个方面:
第一个是点的存储方式,我一开始是自己定义了一个Pair类,然后用这个Pair去计算,这样做很不好,写出来的代码非常难看,而且效率很低(new一个对象是很费时间的)明明一个简单的数组就可以存的东西,为什么去建立一个新的类?
第二个是四个方向的处理方式,我之前也想到了应该用一个for-each循环去处理,但是一直没有想到具体应该怎么实现,我甚至已经准备去手动把四个方向都列出来,但是我实在下不去手写这种屎一样的代码,于是借鉴了一下标准答案,这才意识到建立一个新的fields就可以解决问题。
import java.util.*;
class Solution {
private ArrayList <int[]> directions = new ArrayList<int[]>();
public void wallsAndGates(int[][] rooms) {
directions.add(new int[] {0,1});
directions.add(new int[] {0,-1});
directions.add(new int[] {1,0});
directions.add(new int[] {-1,0});
for(int i = 0; i < rooms.length; i++) {
for(int j = 0; j < rooms[i].length; j++) {
//rooms[i][j] is a gate
if(rooms[i][j] == 0) {
LinkedList<int[]> queue= new LinkedList<int[]>();
queue.offer(new int[] {i,j});
while(!queue.isEmpty()) {
int[] node = queue.poll();
for(int[] dir: directions) {
int[] temp = {0,0};
temp[0] = node[0] + dir[0];
temp[1] = node[1] + dir[1];
if(temp[0] < 0 || temp[0] >= rooms.length || temp[1] < 0 || temp[1] >= rooms[i].length
|| rooms[temp[0]][temp[1]] == 0)
continue;
if(rooms[temp[0]][temp[1]] != -1) {
if (rooms[temp[0]][temp[1]] > rooms[node[0]][node[1]] + 1) {
rooms[temp[0]][temp[1]] = rooms[node[0]][node[1]] + 1;
queue.offer(new int[] {temp[0],temp[1]});
}
}
}
}
}
}
}
}
}
这个是我写的算法,我的算法复杂的是O(mn),和标准答案一样,但其实我这个算法实际运行实际是标准答案的k倍,k的大小是这个矩阵中gate的个数,我的算法遍历了整个图k遍,而标准答案只遍历了一遍。
标准答案把每个gate先加入到了queue中,所以实际上是每个gate用round-robin的方式来遍历整个图,走过的点就不会走第二次(rooms[r][c] != EMPTY)。
我的算法是对每个gate都用BFS走一遍矩阵,所以有k个gate我就得遍历k遍,所以就很蠢,不过好歹是自己写的,总比直接抄答案强。