# SPOJ solution of GRAVITY

I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine whether it is possible to find a path from the 'S' square to the 'T' square, moving using the space squares and avoiding '#' obstacles, in at most O steps (diagonal steps allowed).

I am using normal BFS but I am getting TLE. The time limit is 2 sec and my code should easily run within this limit.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair <int , int > pii;

#define INF (1000000000)
#define ull unsigned long long
#define s(n) scanf("%d",&n)
#define s2(a,b) scanf("%d %d",&a,&b)
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)

int O,m,n;
int dr[]={0,0,-1,1,1,1,-1,-1}; //right,left,up,down,down-right,down-left,up-right,up-left
int dc[]={1,-1,0,0,1,-1,1,-1};
int inRange(int a,int b){ if(a>=0 && a<m && b>=0 && b<n) return 1;return 0;}

char arr[101][101];map <pii,int > dist;

int bfs(int a,int b)
{
queue <pii> q;
dist[pii(a,b)]=0;
q.push(pii(a,b));
while(!q.empty())
{
pii front=q.front();q.pop();
a=front.first;b=front.second;
for(int i=0;i<8;i++)
{
int x=a+dr[i],y=b+dc[i];

if(inRange(x,y) && arr[x][y]!='#' && dist[pii(x,y)]==INF)
{
dist[pii(x,y)]=dist[pii(a,b)]+1;
q.push(pii(x,y));
}
if(inRange(x,y) && arr[x][y]=='T')
{
dist[pii(x,y)]=dist[pii(a,b)]+1;
return dist[pii(x,y)];
}
}
}
return INF;
}

int main()
{
int t;
s(t);
while(t--)
{

int Sx=-1,Sy=-1,Tx=-1,Ty=-1;
s3(O,m,n);
char ch;
scanf("%c",&ch);    //for end of line character

dist.clear();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%c",&ch);
arr[i][j]=ch;
dist[pii(i,j)]=INF;
if(arr[i][j]=='S')
Sx=i,Sy=j;
if(arr[i][j]=='T')
Tx=i,Ty=j;
}
scanf("%c",&ch);   //for end of line character
}

if(Sx==-1 || Sy==-1 || Tx==-1 || Ty==-1)
{
printf("Impossible\n");
continue;
}
int val=bfs(Sx,Sy);
if(val <= O)
printf("Possible\n");
else
printf("Impossible\n");
}
return 0;
}


1. You should pass O to your bsf and terminate it, once you reach zero oxigen. Big map with low O can cause TLE.

2. You don't need the map, you can reuse the array and just mark visited spots (e.g. with '*'). This would be wave algorithm (handle all nodes in the queue at the start of the step, reduce counter O and proceed to next step, unless T or zero O reached). This is simplification of Dijkstra algorithm for graph with all weights=1.

3. Your code is hard to read. You are on Code Review! You are using C++ but program like in old C. Use typedef instead of #define when possible, avoid super-shortcuts like s and s2, please.

This #define here:

#define ull unsigned long long


Should be changed to a typedef instead, like this:

typedef unsigned long long ull;


This line here:

#define ll long long


Should also be changed to this:

typedef long long ll;


In general, if you're using #define to shorten type names, you should be using typedef instead.

You should also drop this line here:

using namespace std;


There are many things that can happen if you have this line, especially if you're working on a large project, and none of them are good. See this Stackoverflow answer for more details.

There's also a reason it's named std and not standard. The prefix std is shorter.

Your inRange function should return a bool, like this:

bool inRange(int x, int y)
{
return x >= 0 && a < m && y >= 0 && y < n;
}


This eliminates the need for the if statements.

Instead of defining your own custom infinity (INF), you should be using std::numeric_limits<T>::infinity().

Finally, you don't need to return 0; in main. main is a special function, so the compiler will automatically insert return 0; if it isn't there.

I cannot review the content of your code because it is very, very unreadable, but I just wanted to point a few things out.

According to the signature, bfs is supposed to return an int.

However, run of the return cases is INF, which is merely a constant assigned to (1000000000); that's not necessarily an int.

Therefore, when creating the constant INF, you should use const and a type. This will ensure that INF is actually and int.

const int INF = 1000000000;


You variable names are very poor. Here are just a few:

int O,m,n;


Your variable names should describe what the variable is used for and/or what it means; this allows anyone reading your code (that includes you if you were to step away from the code for a while).

Having short, one-letter names or cryptic acronyms does only hurts your code. I wanted to review more of your code, but I could not understand a thing because your variable names said nothing.

While I agree with EthanBierlein's points about the #define vs typedef, there is something that I believe he missed: you don't use ull nor do you use ll at all in your code.

I did a little CTRL + Fing through your code and not a single ull or ll turned up.

You can just get rid of these.

There are many things to be said about your style, so I'm just going to brush through them very quickly.

• Spacing. Your lines are very cramped, like here:

if(arr[i][j]=='T')


Add some spaces in here, like around the ==

• You should always use braces in your if statements and loops. If you one day didn't notice these for even a second and then you added something to your code around, you could be in for a tough debugging session.