### PROBLEM LINK:

**Setter:** Kirill Gulin

**Tester:** Misha Chorniy

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Simple

### PREREQUISITES:

BFS, Max-heap/Priority Queue, Greedy

### PROBLEM:

Given a N*M grid with certain **forbidden cells** (represented by -1) where Chef cannot enter, **Empty cells** (represented by 0) where chef can enter and exit, and **Escape Cells** (represented by x>0) using which Chef can escape from grid **if he can reach escape cell from any cell within x seconds**, i.e. the distance from escape cell must be at most x.

Chef can only move from one cell to another if they share an edge.

Find out from which Non-Forbidden cells from where the chef escape and print it in specified format.

### STRATEGY TO SOLVE

**A Tempting greedy but Wrong solution**

The intuitive idea to solve this problem is **For every node with value Greater than 0, run a BFS, mark the node as visited and terminating BFS when distance become greater than x.** This strategy fail for following test case:

1

5 5

0 0 0 0 0

0 0 0 0 0

0 0 0 2 4

0 0 0 0 0

0 0 0 0 0

In this case, if we visit the position with value 2 first, we will either have to reprocess the same position with value 3 (while processing 4), thus getting either TLE or WA, depending upon implementation.

**Why above solution doesnâ€™t work**

Suppose we process a position with lower grid value first. Then later, it might happen, that we visit the same node with higher value of x. Here, if we choose to process it again, we will get TLE in 2nd subtask, because our solution become O((N*M)^2) in worst case. If we choose not to process this vertex again, there is a the possibility that a node earlier not reachable with initial grid value, now become reachable with higher value of x, thus giving us WA.

This gives shape to the ideal strategy to get the correct solution.

##Correct Solution:

**The element with maximum value should be processed first of all.**

Now, this way, whenever we reach a position already visited, we can simply ignore it because we have already processed this position with a higher value of x, Thus, keeping Time Complexity to O(N*M*log(N*M)) (Log factor added for insert and delete operations of Max-heap.

Our final solution become to maintain a max-heap, running a BFS. Due care must be taken to ensure that a position does not get inserted into heap twice, to keep our solution within time limit.

##Testerâ€™s implementation: An O(N*M + maxA) spproach.

With the same idea, Tester made a vector V array of size max(A) , storing all the position (i,j) in V[grid*[j]] for grid*[j]>0. This way, we run a loop from maxA to 0, and for each position in V[x], we add all its neighbours **which are not already processed** into V[x-1] and also mark them as visited.

This way, we save the Log factor associated with insertion in max-heap, thus, getting O(N*M+maxA) runtime.

**Complexity**:

Time Complexity is O(N*M+maxA) or O(M*N*log(M*N)), depending upon implementation.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Setterâ€™s solution

Testerâ€™s solution

Editorialistâ€™s solution