# 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.141592653589793using 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 Endconst 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;}`