SPOJ solution of GRAVITY

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.