一个关于ccf2016年4月份第四题的问题

Question

一个带上时间维度的bfs，代码比较简单，几十行，逻辑较为简单，但是结果是超时，感觉在这个基础上优化算法的可能性也不是很大，麻烦走过路过的大佬帮在下看看哪里出了问题

下面是题目：

这是本人的代码：

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

const int r_rem[4]={0,0,1,-1};
const int c_rem[4]={1,-1,0,0};
int dan_be[100+10][100+10];
int dan_en[100+10][100+10];

class loc
{
    public:
    int r; int c;int t;
    loc(int a1,int a2,int a3);
};

loc::loc(int a1,int a2,int a3)
{
    this->r=a1;this->c=a2;this->t=a3;
}

int bfs(loc now,int row_num,int column_num)
{
    queue<loc> Q;
    Q.push(now);
    while(!Q.empty())
    {
        loc tem=Q.front();
        Q.pop();
        if(tem.r==row_num&&tem.c==column_num)
        return tem.t;

        for(int n=0;n<4;n++)
        {
            if((tem.t+1<dan_be[tem.r+r_rem[n]][tem.c+c_rem[n]]||tem.t+1>dan_en[tem.r+r_rem[n]][tem.c+c_rem[n]])&&
            tem.r+r_rem[n]>0&&tem.r+r_rem[n]<=row_num&&tem.c+c_rem[n]>0&&tem.c+c_rem[n]<=column_num)
            {
                loc next(tem.r+r_rem[n],tem.c+c_rem[n],tem.t+1);
                Q.push(next);
            }
        }
    }
}

int main()
{
    memset(dan_be,-1,sizeof(dan_be));
    memset(dan_en,-1,sizeof(dan_en));

    int row_num=0,column_num=0,dan_num=0;
    cin>>row_num>>column_num>>dan_num;

    for(int n=0;n<dan_num;n++)
    {
        int t1=0,t2=0,t3=0,t4=0;
        cin>>t1>>t2>>t3>>t4;
        dan_be[t1][t2]=t3;
        dan_en[t1][t2]=t4;
    }

    loc now(1,1,0);
    cout<<bfs(now,row_num,column_num);
    return 0;
}

Answer 1

找到参考的代码，用了类似的算法，在具体的数据表达上更高效些，可能可以帮到你。
https://blog.csdn.net/wl16wzl/article/details/79339175
https://blog.csdn.net/tigerisland45/article/details/54934916