1

我正在解决 spoj 上的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);
    }
}
4

0 回答 0