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