HDU 1728迷宮を脱出DFS練習問題

1315 ワード

この問題は単純にDFSで実現するのは難しくないが,関数に回転数のパラメータを加えればよい.この問題を手に入れたばかりで、私も確かにそうしました.
しかし、コードを提出した後、DFSのよくある問題--タイムアウトが発生しました.その後、ディスカッションエリアでは、大部門ACのコードが使用されているBFS+優先キューであることがわかりました.DFSが書かれているので、変更したくないので、DFSがACに成功することもあります.大牛のコードを見て、配列を加えて枝を切ることを知っていればいい.
#include 
#include 
#include 

using namespace std;

int to[4][2]={1,0,-1,0,0,1,0,-1};
char map[105][105];
int turn[105][105];
int sx,sy,ex,ey,swerve,nowtime;
bool endn=false;
int m,n;

void dfs(int x,int y,int flag){
    if(nowtime>swerve) return;
    if(x==ex&&y==ey){
        endn=true;
    }
    if(endn) return;
    //cout<>t;
    while(t--){
        endn=false;
        memset(map,0,sizeof(map));
        memset(turn,999999,sizeof(turn));    //           ,                。
        nowtime=0;
        cin>>m>>n;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                cin>>map[i][j];
            }
        //cout<>swerve>>sy>>sx>>ey>>ex;
        turn[sx][sy]=0;
        dfs(sx,sy,0);
        if(endn) cout<