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
using namespace std;
#define ll long long
typedef pair 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=0 && b dist;

int bfs(int a,int b)
{
queue 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;

-
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.

StackExchange Code Review Q#101808, answer score: 5