Click here to see the full article post
Since you have already find the frontier element for a region in DFS(), you don't need to do it again in the containVirus() , just change those frontier element from 1 to 0 is okay.
@yuryant I agreed with you.
see the following codes:
#Triage the most infectious region, and spread the rest of the regions. for i, reg in enumerate(regions): if i == triage_index: for r, c in reg: grid[r][c] = -1 else: for r, c in frontiers[i]: grid[r][c] = 1
it seems the above code is a little faster. but should be benchmarked.
viral regions that are alive must have size at least t^2 + (t-1)^2t？ and why
the total number removed across all time is Ω(t^3 )≤R∗C?
@FannyChung its wrong.
He is probably assuming that the viruses aren't bounded by the grid borders.
If grid is a line, say 1C, then viral region size at time t is at most O(t). So then we have up to O(C^(1/2)) iterations, and the time complexity is O(RC)^3/2.
To be fair, the input size is bounded by R, C < 50, so the worst case input size is where R == C, and for such a case, it is very plausible that, in the worst case, size of viral region is at time t is still O(t^2)
@awice ,can you please explain why did you use the condition !seen.contains(r*C + c)) in if statement?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.