BFS走迷宫传送门超时怎么改进啊？

Question

第一次提问哈- -，想知道1000ms不超时的解决方法，比较笨
告诉我下思路或f'xiang就可以了

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

char m[100][100];
int r,c;
int sc,sr;
int ec,er;
int d[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
typedef struct
{
    int c;
    int r;
    int step;
} LOC;
struct
{
    int sc;
    int sr;
    int ec;
    int er;
} P[100];

int main()
{
    freopen("data.txt","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>c>>r;
        getchar();
        for(int i=0; i<c; i++)
            gets(m[i]);
        int W;
        cin>>W;
        for(int i=0; i<W; i++)
        {
            cin>>P[i].sc>>P[i].sr>>P[i].ec>>P[i].er;
        }
        cin>>sc>>sr;
        cin>>ec>>er;
        queue<LOC> qu;
        LOC cur;
        cur.c=sc;
        cur.r=sr;
        cur.step=0;
        qu.push(cur);
        int flag;
here:
        while(!qu.empty())
        {
            flag=0;
            cur=qu.front();
            qu.pop();
            if((cur.c==ec)&&(cur.r==er))
            {
                cout<<cur.step<<endl;
                flag=1;
                break;
            }
            for(int i=0; i<W; i++)
            {
                if(P[i].sc == cur.c && P[i].sr == cur.r)
                {
                    if(m[P[i].ec][P[i].er]=='0')
                    {
                        LOC New;
                        New.c=P[i].ec;
                        New.r=P[i].er;
                        New.step=cur.step+1;
                        m[New.c][New.r]='1';
                        qu.push(New);
                    }
                    goto here;
                }
            }
            for(int i=0; i<4; i++)
            {
                LOC New;
                New.c=cur.c+d[i][0];
                New.r=cur.r+d[i][1];
                if(New.c<0||New.c>c-1||New.r<0||New.r>r-1||m[New.c][New.r]=='1')
                    continue;
                New.step=cur.step+1;
                m[New.c][New.r]='1';
                qu.push(New);
            }
        }
        if(!flag)
        cout<<"die"<<endl;
    }
    return 0;
}

Answer 1

用DFS走迷宫。 BFS不适合走迷宫。