найти самый длинный путь, используя BFS

Я решаю ABCPATH проблема на спой, но не удалось из-за: превышен лимит времени (TLE):

Я использовал поиск в ширину (BFS), чтобы найти самый длинный путь, но не знаю, как его оптимизировать. Мой код:

http://ideone.com/RN0QSe

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <string>
#include <numeric>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;
#define MAX 55
#define pii pair< int, int>
char grid[MAX][MAX],c,str[MAX];
int n, m;
bool inRange(int i, int j)
{
return (i>=0 && i<n && j>=0 && j<m);
}
int main()
{
int i, j;
pii p;
queue< pii > Q;
queue<pii>Q1;
scanf("%d %d",&n,&m);
while(n!=0)
{
int d=0;
for(i=0; i<n; i++)
{
scanf("%s",str);
for(j=0;j<m;j++)
{
grid[i][j]=str[j];
//printf("%c\n",grid[i][j]);
if(str[j]=='A')
{
//printf("%d %d\n",i,j);
p.first=i;
p.second=j;
Q1.push(p);
}
}
}
while(!Q1.empty())
{
p=Q1.front();
//printf("%d %d\n",p.first,p.second);
Q1.pop();
Q.push(p);
while(!Q.empty())
{
p=Q.front();
i=p.first;
j=p.second;
c=grid[i][j];
Q.pop();
if(inRange(i+1,j) && (int)grid[i+1][j]==(int)grid[i][j]+1)
{
p.first=i+1;
p.second=j;
Q.push(p);
}
if(inRange(i-1,j) && (int)grid[i-1][j]==(int)grid[i][j]+1)
{
p.first=i-1;
p.second=j;
Q.push(p);
}
if(inRange(i,j+1) && (int)grid[i][j+1]==(int)grid[i][j]+1)
{
p.first=i;
p.second=j+1;
Q.push(p);
}
if(inRange(i,j-1) &&(int)grid[i][j-1]==(int)grid[i][j]+1)
{
p.first=i;
p.second=j-1;
Q.push(p);
}
if(inRange(i-1,j-1) &&(int)grid[i-1][j-1]==(int)grid[i][j]+1)
{
p.first=i-1;
p.second=j-1;
Q.push(p);
}
if(inRange(i+1,j+1) &&(int)grid[i+1][j+1]==(int)grid[i][j]+1)
{
p.first=i+1;
p.second=j+1;
Q.push(p);
}
if(inRange(i+1,j-1) &&(int)grid[i+1][j-1]==(int)grid[i][j]+1)
{
p.first=i+1;
p.second=j-1;
Q.push(p);
}
if(inRange(i-1,j+1) &&(int)grid[i-1][j+1]==(int)grid[i][j]+1)
{
p.first=i-1;
p.second=j+1;
Q.push(p);
}
}
if(((int)c-65)>d)
d=((int)c-65);
}
printf("%d\n",d+1);
scanf("%d %d",&n,&m);
}
}