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


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;
}