Connect | Editorial by gg

Connect | Editorial by gg_14

Apply DFS from starting point in the grid and keep the points that are being visited. Let the set of these points be S1.
If destination is reached from the starting point then there is no need to create a tunnel, thus the answer is zero.
Else apply DFS again, this time from the destination point and keep the points that are being visited. Let the set of these points be S2.
Then for every pair of points, one from S1 and one from S2, calculate the cost required to create the tunnel. The minimum of above costs will be the answer.
Sample code:
```
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define ll long long
#define MOD7 1000000007
#define MOD9 1000000009
int n;
vector<string> mat;
int vis[100][100];
void dfs(int i,int j, vector<pair<int,int> > &vec){
	if(i<0 || j<0 || i>=n || j>=n)
		return;
	if(mat[i][j]=='1')
		return;
	vis[i][j]=1;
	vec.pb(mp(i,j));
	if(!vis[i][j+1])
		dfs(i,j+1,vec);
	if(!vis[i+1][j])
		dfs(i+1,j,vec);
	if(!vis[i][j-1])
		dfs(i,j-1,vec);
	if(!vis[i-1][j])
		dfs(i-1,j,vec);
}
int main(){
	scanf("%d",&n);
	int x1,y1,x2,y2;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	string str;
	for(int i=0;i<n;i++){
		cin >> str;
		mat.pb(str);
	}
	memset(vis,0,sizeof(vis));
	x1--;y1--;x2--;y2--;
	vector<pair<int,int> > v1,v2;
	// apply dfs and store the coordinates in v1
	dfs(x1,y1,v1);

// if end point reached, then no tunnel required
	if(vis[x2][y2]){
		printf("0\n");
		return 0;
	}

// apply dfs again and store the coordinates in v2
	dfs(x2,y2,v2);

int ans=MOD9;

// find minimum cost of making a tunnel from
	// a point in v1 to a point in v2	
	for(int i=0;i<v1.size();i++){
		for(int j=0;j<v2.size();j++){
			int temp = (v1[i].f-v2[j].f)*(v1[i].f-v2[j].f)+(v1[i].s-v2[j].s)*(v1[i].s-v2[j].s);
			ans = min(ans,temp);
		}
	}
	printf("%d\n",ans);
	return 0;

}
```

Connect | Editorial by gg_14

Download submission

All caught up!

View submission

Is your resume even shortlisted?