给定一个n乘m的矩阵map,其中map[i][j]表示坐标为(i,j)的格子,值为1代表该格子不能通过,0代表可以通过。现从(0,0)的格子走到(n - 1,m - 1),单位时间只能走一格,不能途径无法通过的格子,请返回最短时间。同时给定矩阵的大小n和m(n和m均小于等于100),并且一定能走到终点。
class Flood: def floodFill(self, tmap, n, m): return n+m-2
class Flood: def __init__(self): self.nm={} def floodFill(self, tmap, n, m): if n==1 and m==1: return 0 i=len(tmap)-n j=len(tmap[0])-m if tmap[i][j]!=0: self.nm[(i,j)]=10000 return 10000 if n!=1: try: sn=self.nm[(i+1,j)]+1 except: sn=self.floodFill(tmap,len(tmap)-i-1,len(tmap[0])-j)+1 if m!=1: try: sm=self.nm[(i,j+1)]+1 except: sm=self.floodFill(tmap,len(tmap)-i,len(tmap[0])-j-1)+1 try: min_num=min(sn,sm) self.nm[(i,j)]=min_num return min_num except: try: tmap[i][j]=sn return sn except: tmap[i][j]=sm return sm
# -*- coding:utf-8 -*- class Flood: def floodFill(self, tmap, n, m): dp = [[10000000] * (m + 2) for i in range(n + 2)] dp[1][1] = 0 for i in range(n): for j in range(m): if i == 0 and j == 0: continue if tmap[i][j] == 0: dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i + 2][j + 1], dp[i + 1][j + 2]) + 1 return dp[n][m]
# -*- coding:utf-8 -*- from collections import deque class Flood: def floodFill_bfs(self, tmap, n, m): queue = deque() queue.append((0, 0)) distance = {} distance[(0, 0)] = 0 self.n = n self.m = m self.tmap = tmap while queue: cur = queue.popleft() for next in self.graphNeighbors(cur): if next not in distance: queue.append(next) distance[next] = 1 + distance[cur] return distance[(n - 1, m - 1)] def graphNeighbors(self, point): i = point[0] j = point[1] neighbors = [] if 0 <= i - 1 < self.n and self.tmap[i - 1][j] == 0: neighbors.append((i - 1, j)) if 0 <= i + 1 < self.n and self.tmap[i + 1][j] == 0: neighbors.append((i + 1, j)) if 0 <= j - 1 < self.m and self.tmap[i][j - 1] == 0: neighbors.append((i, j - 1)) if 0 <= j + 1 < self.m and self.tmap[i][j + 1] == 0: neighbors.append((i, j + 1)) return neighbors