HDOJ 1175 연속적으로 DFS BFS 를 보다

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1175
사고: DFS 에 dir, turn 을 추가 하여 각각 방향, 커 브 횟수 를 표시 합 니 다. turn 이 2 회 를 초과 하면 반드시 돌아 가 야 합 니 다. DFS 는 가 지 를 잘라 야 합 니 다. 그렇지 않 으 면 시간 을 초과 합 니 다. 아래 코드: 593 MS 3348 K
DFS 코드 먼저 올 리 기:

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
using namespace std;
int maze[1010][1010];
bool visit[1010][1010];
int y;
int n,m,x1,x2,y2;
bool flag;
void dfs(int x1,int y1,int dir,int turn)// dir:  ，turn:     
{
	if(x1<=0||x1>n||y1<=0||y1>m)return ;//   
	if(flag)return ;    //    
	if(turn>=3)return ;  //    2    
	if(x1==x2&y1==y2){
		flag=1;
		return ;
	}
	if(turn==2){       //    ：     2 ，   x2,y2 x1,y1            
		if( !(dir==1&&x1>x2&&y1==y2||dir==2&&x1<x2&&y1==y2||dir==3&&y1>y2&&x1==x2||dir==4&&y1<y2&&x1==x2) )
			return ; 
	}
	if(maze[x1][y1]!=0)return ;  
	if(visit[x1][y1])return ;
	visit[x1][y1]=1;
	if(dir==1){            //   ， dir==1  ，      ，1：     ，  
	                       //2：   ，   ，3：   ，   。    。 
		dfs(x1-1,y1,1,turn);
		dfs(x1,y1-1,3,turn+1);
		dfs(x1,y1+1,4,turn+1);
	} 
	else if(dir==2){
		dfs(x1+1,y1,2,turn);
		dfs(x1,y1-1,3,turn+1);
		dfs(x1,y1+1,4,turn+1);
	}
	else if(dir==3){
		dfs(x1-1,y1,1,turn+1);
		dfs(x1+1,y1,2,turn+1);
		dfs(x1,y1-1,3,turn);
	}
	else if(dir==4){
		dfs(x1-1,y1,1,turn+1);
		dfs(x1+1,y1,2,turn+1);
		dfs(x1,y1+1,4,turn);
	}
	visit[x1][y1]=0;
}
int main()
{
	while(cin>>n>>m)
	{
		if(n==0&&m==0)break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>maze[i][j];
		int q;
		cin>>q;
		while(q--)
		{
			cin>>x1>>y>>x2>>y2;
			flag=0;
			if(x1==x2&&y==y2){
				cout<<"NO"<<endl;
				continue;
			}
			if(maze[x1][y]!=maze[x2][y2]||maze[x1][y]==0||maze[x2][y2]==0){
				cout<<"NO"<<endl;
				continue;
			}
			                 //     ，         ，      0      
			memset(visit,false,sizeof(visit));
			flag=0;
			
			dfs(x1-1,y,1,0); //  
			dfs(x1+1,y,2,0); //  
			dfs(x1,y-1,3,0); //  
			dfs(x1,y+1,4,0); //  
			if(flag)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}		
		
	}
	return 0;

}

 

bfs 의 코드 효율 이 비교적 낮 습 니 다. 저 는 dfs 시간 복잡 도가 bfs 보다 높다 고 생각 했 습 니 다. 그러나 가지치기 관계 로 인해 이 문제 bfs 의 AC 시간 은 2718 MS, 4 배의 차이 입 니 다. 먼저 코드 를 연구 한 다음 에 다시 이야기 하 겠 습 니 다.

 #include <iostream>
 #include <queue>
 using namespace std;
 
 const int N = 1001;
 bool flag;
 int n,m,sx,sy,ex,ey;
 int hash[N][N],map[N][N];
 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
 struct node{
     int x,y,turn,d;
}start;
queue<node> q;

inline bool in(const node &p){
     if(p.x<0 || p.y<0 || p.x>=n || p.y>=m)
        return false;
     return true;
 }
void bfs(){
     node now,t;
    while(!q.empty()){
         now=q.front(),q.pop();
         if(now.x==ex && now.y==ey && now.turn<=2){
             flag=true;
             return;
         }
         for(int i=0;i<4;i++){
             t.x=now.x+dir[i][0],t.y=now.y+dir[i][1];
             if(now.d==i)
                 t.turn=now.turn,t.d=now.d;
             else
                 t.turn=now.turn+1,t.d=i;
            if(in(t) && (map[t.x][t.y]==0||t.x==ex&&t.y==ey) && hash[t.x][t.y]>=t.turn)
                 hash[t.x][t.y]=t.turn,q.push(t);
         }
     }
 }
 int main(){
     int i,j,t;
     while(scanf("%d %d",&n,&m),n||m){
        for(i=0;i<n;i++)
             for(j=0;j<m;j++) scanf("%d",&map[i][j]);
         scanf("%d",&t);
         while(t--){
             scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
             sx--,sy--,ex--,ey--;
             if((map[sx][sy]!=map[ex][ey]) || map[sx][sy]==0 || map[ex][ey]==0 || (sx==ex&&sy==ey)){
                 puts("NO");
                 continue;
             }
             for(i=0;i<n;i++)
                for(j=0;j<m;j++) hash[i][j]=11;
             while(!q.empty()) q.pop();
             for(i=0;i<4;i++){
                 start.x=sx,start.y=sy,start.turn=0,start.d=i;
                 q.push(start);
             }
             flag=false,hash[sx][sy]=0;
             bfs();
             puts(flag ? "YES":"NO");
         }
     }
   return 0; }