grid, C++ (gcc) - rextester

grid

#include<bits/stdc++.h>
using namespace std;

#define mem(A) memset(A,0,sizeof(A))
#define loop(i,a,n) for(long long i=a;i<n;i++)
#define pb push_back
#define mkp make_pair
#define prq priority_queue
#define fir first
#define sec second
#define all(A) A.begin(),A.end()
#define mod 1000000007
#define take(t) ll t;cin>>t;while(t--)

typedef long long ll;
typedef pair<ll,ll> pll;

ll M[1002][1002],V[1002][1002],n,m;
ll func(string s[],ll xi,ll yi,ll xd,ll yd)
{
    if(xd<0 || yd<0 || xd>=n || yd>=m)
        return INT_MAX;
    if(xi==xd && yi==yd)
        return 0;
    if(s[xd][yd]=='*')
        return INT_MAX;
    if(V[xd][yd])
        return INT_MAX;
    if(M[xd][yd]==0)
    {ll a,b,ax,ay;
    V[xd][yd]=1;
        a=func(s,xi,yi,xd,yd-1);
        ax=xd,ay=yd-1;
        b=func(s,xi,yi,xd-1,yd);
        if(a>b)
         ax=xd-1,ay=yd,a=b;
        b=func(s,xi,yi,xd,yd+1);
        if(a>b)
         ax=xd,ay=yd+1,a=b;
        b=func(s,xi,yi,xd+1,yd);
        V[xd][yd]=0;
        
        if(a>b)
          ax=xd+1,ay=yd,a=b;
        V[ax][ay]=1;
        M[xd][yd]=a+1;
    }
    return M[xd][yd];
}
int main()
{   //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

ll q,xi,yi,xd,yd;

cin>>n>>m>>q;
    string s[n];
    loop(i,0,n)
     cin>>s[i];
    cin>>xi>>yi;
    mem(M);
    while(q--)
    {   mem(V);
        cin>>xd>>yd;
        ll ans=func(s,xi-1,yi-1,xd-1,yd-1);
        if(ans>=INT_MAX)
            ans=-1;
        cout<<ans<<endl;
    }
}


run \| edit \| history \| help	0