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 &lt;bits/stdc++.h&gt;
using namespace std;
#define ll long long
typedef pair &lt;int , int &gt; pii;

#define INF (1000000000)
#define ull unsigned long long
#define s(n) scanf("%d",&amp;n)
#define s2(a,b) scanf("%d %d",&amp;a,&amp;b)
#define s3(a,b,c) scanf("%d %d %d",&amp;a,&amp;b,&amp;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&gt;=0 &amp;&amp; a&lt;m &amp;&amp; b&gt;=0 &amp;&amp; b&lt;n) return 1;return 0;}


char arr[101][101];map &lt;pii,int &gt; dist;


int bfs(int a,int b)
{
    queue &lt;pii&gt; 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&lt;8;i++)
        {
            int x=a+dr[i],y=b+dc[i];

            if(inRange(x,y) &amp;&amp; arr[x][y]!='#' &amp;&amp; dist[pii(x,y)]==INF)
            {
                dist[pii(x,y)]=dist[pii(a,b)]+1;
                q.push(pii(x,y));
            }
            if(inRange(x,y) &amp;&amp; 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",&amp;ch);    //for end of line character

        dist.clear();
        for(int i=0;i&lt;m;i++)
        {
            for(int j=0;j&lt;n;j++)
            {
                scanf("%c",&amp;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",&amp;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 &lt;= O)
            printf("Possible\n");
        else
             printf("Impossible\n");
    }
    return 0;
}
You should pass O to your bsf and terminate it, once you reach zero oxigen. Big map with low O can cause TLE.
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.
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.