I thought it is a straightforward BFS search, so I write it like the following.
Actually, I have the same question with
Number of Island problem:
import collections class Solution(object): def cutOffTree(self, G): """ :type forest: List[List[int]] :rtype: int """ if not G or not G: return -1 m, n = len(G), len(G) trees =  for i in xrange(m): for j in xrange(n): if G[i][j] > 1: trees.append((G[i][j], i, j)) trees = sorted(trees) count = 0 cx, cy = 0, 0 for h, x, y in trees: step = self.BFS(G, cx, cy, x, y) if step == -1: return -1 else: count += step G[x][y] = 1 cx, cy = x, y return count def BFS(self, G, cx, cy, tx, ty): m, n = len(G), len(G) visited = [[False for j in xrange(n)] for i in xrange(m)] Q = collections.deque() step = -1 Q.append((cx, cy)) while len(Q) > 0: size = len(Q) step += 1 for i in xrange(size): x, y = Q.popleft() visited[x][y] = True if x == tx and y == ty: return step for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]: if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]: continue Q.append((nx, ny)) return -1
visited[x][y] = True
should be put in
for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]: if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]: continue Q.append((nx, ny)) The visited[x][y] = True
if you put it there, you might visite the position many times. And that leads to TLE.
I just have the same problem with you.
Same problem here. I think the time allowed for this question for python is not correct.
def BFS(self, G, cx, cy, tx, ty):
If you need to do BFS from
(tx,ty), instead of doing BFS from
(cx,cy) only, you can do two-way BFS both from
For example, to find the minimum step from C to T, X is obstacle.
Doing two-way BFS step by step:
[C, , , ] [ , ,X, ] [ ,X, , ] [ ,X, ,T] [0,1, , ] [1, ,X, ] [ ,X, ,1] [ ,X,1,0] [0,1,2, ] [1,2,X,2] [2,X,2,1] [ ,X,1,0] [0,1,2,3] <--- two BFS meet '3' here [1,2,X,2] [2,X,2,1] [3,X,1,0]
step = 3+3 = 6
I think it works faster.
Another optimization is, saying you are cutting tree from height 5 to height 6, and the next tree after 6 is 7, after finding the shortest path from 5 to 6, if 7 is within the shortest path, then you don't need to do another BFS from 6 to 7 again.
Shortest path from 5->6 :
5 --(4 step)--> 7 --(6 step)--> 6
5 -> 6 : 10 step
6 -> 7 must be 6 step.
I kept getting TLE during the contest, too. I went through the top 50 people's code after the contest, and it seemed that none of them used Python. I think the allowed time is unfair for Python programmers.
Note: I did set visited[x][y] = True before putting x,y into the queue.
@niwota Hi, I tried two-way BFS and it still says TLE..
I tried to set the visited flag before adding it into the queue, i still get TLE...
@mainarke Nobody during the contest, two people after the contest. One in their eleventh attempt (four of the failures were TLE) and the other in their fifth attempt (three of the failures were TLE).
@StefanPochmann Actually, the first "solver" doesn't have a real solution, their code starts with
if forest == 46362: return 65669 and two more of those.
But the second solver's solution is legitimate. It does do independent shortest-path searches from each tree to the next, but uses something somewhat better than BFS (and some optimizations). An algorithm I didn't know before, and which is quite interesting. I asked them to share it here in the forum.
And now a third person did it but cheated just like the first (at least in the few submissions I checked, they submitted so many I'm not going to check all of them).
@StefanPochmann Thanks for the information. Looking forward to the brilliant solution from the second solver.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.