286 Walls and Gates
286. Walls and Gates
题目： https://leetcode.com/problems/walls-and-gates/
难度 : Medium
思路：
乍一看feel like all pairs shortest path.
naive的想法是针对所有为0的点做all pairs shortest path，然后最终得到的就是把INF替换保留最小的。时间复杂度是0的个数* BFS
naive的想法AC
class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
def legal(x,y):
return x >= 0 and x < row and y >= 0 and y < col and rooms[x][y] != -1
def bfs(rooms, i, j):
queue = []
queue.append((i,j))
while queue:
(x,y) = queue.pop()
if legal(x-1,y) and rooms[x-1][y] > rooms[x][y] + 1:
rooms[x-1][y] = rooms[x][y] + 1
queue.append((x-1,y))
if legal(x+1,y) and rooms[x+1][y] > rooms[x][y] + 1 :
rooms[x+1][y] = rooms[x][y] + 1
queue.append((x+1,y))
if legal(x,y-1) and rooms[x][y-1] > rooms[x][y] + 1:
rooms[x][y-1] = rooms[x][y] + 1
queue.append((x,y-1))
if legal(x,y+1) and rooms[x][y+1] > rooms[x][y] + 1 :
rooms[x][y+1] = rooms[x][y] + 1
queue.append((x,y+1))
row = len(rooms)
col = len(rooms[0]) if row else 0
for i in range(row):
for j in range(col):
if rooms[i][j] == 0:
bfs(rooms,i,j)
复习一下BFS的伪码
from wikipedia, 一开始有点小迷茫，那就是为什么没有keep一个visited的数据结构，但是随即反应过来，其实n.distance == INFINITY 已经是check它是否被visited 过了，我以上的代码并没有做这个操作，但是因为是格子状以及我仅在检查是否更小，所以也能AC.
Breadth-First-Search(Graph, root):
for each node n in Graph:
n.distance = INFINITY
n.parent = NIL
create empty queue Q
root.distance = 0
Q.enqueue(root)
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n.distance == INFINITY:
n.distance = current.distance + 1
n.parent = current
Q.enqueue(n)
