is this not a problem of Dp where we test out all possible paths for all 0’s in the matrix and for each 0 we return the minimum number of 1’s encountered and then finally take max of all those returned values ?
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
}
Problem Link: Prison Escape Practice Coding Problem
Your question looks like a paraphrase of the problem statement. However you should consider time restriction: ‘0’ may occur up to n*m ~ 3 * 10**5 times, that leaves not much room for looking at “all possible paths”.
However this is in its core a minimal distance problem (distance from the outside to any ‘0’, where any ‘1’ on the way adds 1 to the distance). So you could have a look at Dijkstra’s routing algorithm, starting with the “outside” fields at distance 0, using a minimum heap for the neighboring fields until all fields are reached. Every time you encounter a ‘0’ you have to update the running maximum, which gives the final result.
got it,
thanks