HackerEarth Grid problem solution YASH PAL, 31 July 2024 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("-1n"); else printf("%dn",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;} coding problems