1130C - Connect - CodeForces Solution

//اللَّهُ لَا إِلَٰهَ إِلَّا هُوَ ۚ وَعَلَى اللَّهِ فَلْيَتَوَكَّلِ الْمُؤْمِنُونَ
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define Abdulrhem ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
const long long N=2e5+10,mod=1e9+7;
#define all(x) x.begin(),x.end()
#define take(arr,n) for (int i=0;i<n;i++) cin>>arr[i];
#define f first
#define s second
vector<ll>theprimes;
int n,m;

bool vis[55][55];
int dist[1005][1005];
vector<bool>primes(N,1);
void sieve()
{
    //o(nlogn)
    // memset(primes,1,sizeof primes);
    primes[0]=primes[1]=0;
    for(int i=2;i*i<N;i++)
    {
        if(primes[i])
        {
            //theprimes.push_back(i);
            for(int j=i*2;j<N;j+=i)
                primes[j]=0;
        }
    }
}
pair<int,vector<int>> comp[N];
void modified_seive()
{
    for(int i=0;i<N;i++)
    {
        comp[i].first=i;
        comp[i].second.push_back(i);
    }
    for(int i=2;i*i<N;i++)
    {
        if(comp[i].first==i)
        {
            for(int j=i*2;j<N;j+=i) {
                comp[j].second.push_back(i);
                if (comp[j].first == j)
                    comp[j].first = i;
            }
        }
    }
}
long long gcd(long long a,long long b)
{
    if(b==0)return a;
    else{
        long long rem=a%b;
        return gcd(b,rem);
    }
}
ll lcm(ll a,ll b){
    return a*b / gcd(a,b);
}
ll mul(int x, int y) {
    return 1LL * x * y % mod;
}
ll add(int x, int y) {
    return (x + y) % mod;
}

ll power(int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

ll binarySearch(ll &maxCoins,ll k,ll m,ll l){
    ll left = 1,right = maxCoins;
    ll mid;
    ll ans = -1;
    while(left<=right){
        mid = (left+right)>>1;
        if ((mid*m)-k >= l){
            right = mid -1;
            ans = mid;
        }
        else{
            left = mid +1;
        }
    }
    return ans;
}
bool inRange(int i,set<pair<int,int>>ans){
    i++;
    for (auto it:ans){
        if (i>=it.f&&i<=it.s)return 1;
    }
    return 0;
}
bool allZero (string &b){
    for (auto it:b){
        if (it == '1')return 0;

    }
    return 1;
}
bool allOne(string &b){
    for (auto it:b){
        if (it == '0')return 0;

    }
    return 1;
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char matrix[55][55];

void BFS(int x,int y,set<pair<int,int>>&island){
    vis[x][y]=1;
    queue<pair<int,int>>q;
    q.push({x,y});
    while(!q.empty()){
        int xx=q.front().f;
        int yy = q.front().s;
        //cout<<"am in "<<xx<<" "<<yy<<endl;
        q.pop();
        for (int i=0;i<4;i++){
            int xtmp = xx+dx[i];
            int ytmp = yy + dy[i];

            if (xtmp>=0&&xtmp<n&&ytmp>=0&&ytmp<n){
                if (matrix[xtmp][ytmp]=='0'&&!vis[xtmp][ytmp]){
                    vis[xtmp][ytmp]=1;
                    q.push({xtmp,ytmp});
                }
                else if (matrix[xtmp][ytmp]=='1'){
                    island.insert({xx,yy});
                }
            }
        }
    }
}
void solve(){
    cin>>n;
    int x1,y1,x2,y2;
    cin>>x1>>y1;
    cin>>x2>>y2;
    x1--;
    y1--;
    x2--;
    y2--;
    memset(vis,0,sizeof vis);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    //cout<<"shit"<<endl;
    set<pair<int,int>>island1;
    set<pair<int,int>>island2;
    BFS(x1,y1,island1);
    if (vis[x2][y2]){
        cout<<0<<endl;
        return;
    }
    BFS(x2,y2,island2);
    int ans = INT_MAX;
    for (auto it:island1){
        for (auto itt:island2){
            int x1 = it.f;
            int y1= it.s;
            int x2 = itt.f;
            int y2 = itt.s;
            int tmp = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
            ans = min(ans,tmp);
        }
    }
    cout<<ans<<endl;
}
int main() {
    Abdulrhem;
    //sieve();
    //to erase the first character in string use s.erase(0,1);
    //long double pi = 3.141592653589793238462643383279502884;

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