F6heml - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
#define int              long long int
#define double           long double
#define print(a)         for(auto x : a) cout << x << " "; cout << endl
inline int power(int a, int b) {
    int x = 1;
    while (b) {
        if (b & 1) x *= a;
        a *= a;
        b >>= 1;
    }
    return x;
}


const int M = 1000000007;
const int N = 3e5+9;
const int INF = 2e9+1;
const int LINF = 2000000000000000001;

//_ ***************************** START Below *******************************

vector<vector<int>> a;
vector<vector<int>> dirs = {{0, 1} , {1, 0} , {0, -1}, {-1, 0} };
queue<pair<int,int>> q;
vector<vector<bool>> visited;
vector<vector<int>> lvl;

void dfs(int x, int y, int m, int n){

	visited[x][y] = true;
	a[x][y] = 2;

	bool anyChildZero = false;
	for(auto& dir : dirs){
		int i = x + dir[0];
		int j = y + dir[1];

		if(i<0 || i>=m || j<0 || j>=n) continue;
		if(a[i][j] == 0) anyChildZero = true;

		if(a[i][j] == 0 || visited[i][j]) continue;
		dfs(i, j, m, n);
	}

	if(anyChildZero) q.push({x,y});

}


//* Eg :
//* 	0 0 0 0 0 0 0
//* 	0 1 1 1 0 0 0
//* 	0 1 0 1 0 0 0
//* 	0 1 1 1 0 0 0
//* 	0 0 0 0 0 1 1
//* 	0 0 0 0 1 1 1
//* 	0 0 0 0 0 1 0

//? Interview Approach  :
//* 	Do bfs from all nodes of Island 1 (i.e. internal nodes also )

//* Optimized Approach :
//* 	We are only interested in distance from boundary of island 1 to all other nodes
//* 	Do bfs from Boundary nodes only of Island 1
//* 	Even if bfs find distance of inside nodes of Island 1 , we don tcare,
//* 		we only calculate ans for island 2 later while traversing


//* How to BFS island 1 ?
//* 	1. Store all nodes of island 1 in Hashmap
//* 	   Do boundary bfs from boundary nodes only
//* 	   Island 2 nodes can be identified in O(1) check using Hashmap
//* 					OR
//* 	2. Color the nodes of island 1 (inplace or with separate matrix)
//* 		Island 2 can be identified with a[i][j] == 1 (2 is for Island 1)


void consistency(int m, int n){

	visited.resize(m, vector<bool>(n, false));
	lvl.resize(m, vector<int>(n, 0));

	for(int i=0; i<m; i++){
		bool isFirstIslandTraversed = false;
		for(int j=0; j<n; j++){
			if(a[i][j] == 1) {
				dfs(i,j, m, n);
				isFirstIslandTraversed = true;
				break;
			}
		}
		if(isFirstIslandTraversed) break;
	}


	int mini = INF;

	while(!q.empty()){

		auto u = q.front(); q.pop();

		int x = u.first;
		int y = u.second;

		for(auto& dir : dirs){
			int i = x + dir[0];
			int j = y + dir[1];

			if(i<0 || i>=m || j<0 || j>=n ||  visited[i][j]) continue;
			q.push({i, j});
			visited[i][j] = true;
			lvl[i][j] = lvl[x][y] + 1;

			//* Min Distance calculation
			if(a[i][j] == 1) mini = min(mini, lvl[i][j]);
		}

	}


	//* Further Optimization :
	//* Calculate mini directly above (not here)

	// for(int i=0; i<m; i++){
	// 	for(int j=0; j<n; j++){
	// 		if( a[i][j] == 0 || a[i][j] == 2) continue;
	// 		mini = min(mini, lvl[i][j]);
	// 	}
	// }

	cout << mini-1 << endl;

}


void solve() {

    int m, n;
    cin>>m >> n;
    a.resize(m, vector<int>(n, 0));
    for(int i=0; i<m; i++){
    	for(int j=0; j<n; j++){
    		cin >> a[i][j];
    	}
    }

    consistency(m, n);


}


int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}