HackerEarth Grid problem solution

In this HackerEarth Grid problem solution You are given a grid A of size N X M, two integers (Si,Sj) and Q tasks. Each task contains two integers, (Di,Dj). Each cell in the grid is either empty cells denoted by O (Capital English character 'o') or occupied cells denoted by *. Initially, you are at (Si,Sj). Find the minimum number of steps in which you have to take to reach (Di,Dj) from (Si,Sj) without traversing the occupied cells.

In a single step, you can move from any cell (i,j) to the 4 neighboring cells i.e. (i-1,j), (i+1,j), (i,j-1) and (i,j +1) provided these cells are inside the grid A.

HackerEarth Grid problem solution.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>

#define ll long long int
#define maxN 1000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL

#define gcd(a,b) __gcd(a,b)

using namespace std;

char a[maxN+5][maxN+5];
int d[maxN+5][maxN+5];
set<pair<int,pair<int,int> > > s;
set<pair<int,pair<int,int> > >::iterator it;

int r[]={0,0,1,-1};
int c[]={1,-1,0,0};

int main()
{
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input/in19.txt","r",stdin);
        freopen("input/out19.txt","w",stdout);
    #endif
    int n,m,q,ui,uj,vi,vj,i,j,k;
    scanf("%d%d%d",&n,&m,&q);
    for(i=0;i<n;i++)
    {
      scanf("%s",a[i]);
      for(j=0;j<m;j++)
        d[i][j]=maxVal;
    }
    scanf("%d%d",&ui,&uj);
    d[ui-1][uj-1]=0;
    s.insert(make_pair(0,make_pair(ui-1,uj-1)));
    while(!s.empty())
    {
      it=s.begin();
      ui=(*it).second.first;
      uj=(*it).second.second;
      s.erase(it);
      for(k=0;k<4;k++)
      {
        vi=ui+r[k];
        vj=uj+c[k];
        if(vi>=0&&vi<n&&vj>=0&&vj<m&&a[vi][vj]!='*'&&
          d[vi][vj]>(d[ui][uj]+1))
        {
          if(d[vi][vj]!=maxVal)
            s.erase(s.find(make_pair(d[vi][vj],make_pair(vi,vj))));
          d[vi][vj]=d[ui][uj]+1;
          s.insert(make_pair(d[vi][vj],make_pair(vi,vj)));
        }
      }
    }
    while(q--)
    {
        scanf("%d%d",&ui,&uj);
      if(d[ui-1][uj-1]==maxVal)
        printf("-1\n");
      else
        printf("%d\n",d[ui-1][uj-1]);
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define le length()
#define sz size()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;

// Template End
const int MAX = 1e3 + 5;
string s[MAX];
bool vis[MAX][MAX];
int ans[MAX][MAX];
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, -1, 1};


void bfs(int sx, int sy, int n, int m) {
    queue <PII> q;
    PII p;
    int x, y;
    q.push({sx, sy});
    ans[sx][sy] = 0;
    vis[sx][sy] = true;
    while(!q.empty()) {
        p = q.front();
        q.pop();
        REP(i, 0, 4, 1) {
            x = dr[i] + p.fi;
            y = dc[i] + p.se;
            if (x >= 1 and x <= n and y >= 1 and y <= m and s[x][y] == 'O' and vis[x][y] == false) {
                ans[x][y] = ans[p.fi][p.se] + 1;
                vis[x][y] = true;
                q.push({x, y});
            }
        }
    }
}

int main(int argc, char* argv[]) {
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    ios::sync_with_stdio(false);
    int n, m, q, sx, sy, dx, dy;
    cin >> n >> m >> q;
    assert(1 <= n and n <= 1000);
    assert(1 <= m and m <= 1000);
    assert(1 <= q and q <= 1000000);
    REP(i, 1, n+1, 1) {
        cin >> s[i];
        s[i] = '0' + s[i];
        REP(j, 1, m+1, 1) {
            assert(s[i][j] == 'O' or s[i][j] == '*');
            ans[i][j] = -1;
        }
    }
    cin >> sx >> sy;
    assert(1 <= sx and sx <= 1000);
    assert(1 <= sy and sy <= 1000);
    bfs(sx, sy, n, m);
    while(q--) {
        cin >> dx >> dy;
        assert(1 <= dx and dx <= 1000);
        assert(1 <= dy and dy <= 1000);
        cout << ans[dx][dy] << endl;
    }
    return 0;
}