hdu 1175 연속적으로 DFS 해법 을 보다.입문 DFS 는 괜 찮 은 것 같 아 요.

연거푸 보다
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 21537    Accepted Submission(s): 5355
Problem Description
'보 는 것 도' 많은 사람들 이 해 봤 을 거 라 고 믿 습 니 다.안 해 봐 도 괜찮아 요. 다음은 제 가 게임 규칙 을 소개 해 드릴 게 요. 한 바둑판 에 바둑 알 을 많이 넣 었 어 요.만약 에 똑 같은 두 개의 바둑 알 이 한 개의 선 을 통 해 연결 할 수 있 고 (이 선 은 다른 바둑 알 을 통과 할 수 없다) 선의 전환 횟수 가 두 번 을 초과 하지 않 으 면 이 두 개의 바둑 알 은 바둑판 에서 사라 질 수 있다.죄 송 하지만 저 는 예전 에 계속 놀아 본 적 이 없어 서 친구 들 의 의견 을 물 어 봤 습 니 다. 연결선 은 밖에서 돌아 갈 수 없 지만 사실은 이것 이 틀 렸 습 니 다.지금 은 이미 큰 화 를 일 으 켰 으 니, 잘못 을 바로 잡 을 수 밖 에 없 으 며, 연결선 은 외곽 에서 돌아 갈 수 없다.
유 저 는 마 우 스 를 선후 로 두 개의 바둑 알 을 클릭 하여 그들 을 없 애 려 고 한 다음 에 게임 의 백 스테이지 에서 이 두 개의 격자 가 없어 질 수 있 는 지 없 는 지 판단 합 니 다.지금 당신 의 임 무 는 바로 이 백 스테이지 프로그램 을 쓰 는 것 입 니 다.
 
Input
입력 데이터 가 여러 그룹 입 니 다.각 조 데이터 의 첫 줄 에는 두 개의 정수 n, m (0 < n < = 1000, 0 < m < 1000) 가 있 는데 각각 바둑판 의 줄 수 와 열 수 를 나타 낸다.다음 n 줄 에서 줄 마다 m 개의 비 마이너스 정수 가 바둑판 의 격자 분 포 를 묘사 합 니 다.0 은 이 위치 에 바둑 알 이 없다 는 것 을 나타 내 고 정 수 는 바둑 알 의 유형 을 나타 낸다.다음 줄 은 정수 q (0 < q < 50) 로 아래 에 q 번 의 문의 가 있 음 을 나타 낸다.다음 q 줄 에 서 는 각 줄 에 네 개의 정수 x1, y1, x2, y2 가 있 는데, x1 줄 y1 열의 바둑 알 과 x2 줄 y2 열의 바둑 알 이 없어 질 수 있 는 지 물 어 보 는 것 을 나타 낸다.n = 0, m = 0 시 입력 이 끝 납 니 다.
주의: 문의 간 에 선후 관계 가 없 는 것 은 모두 현재 상 태 를 겨냥 한 것 입 니 다!
 
Output
각 그룹의 입력 데 이 터 는 한 줄 의 출력 에 대응 합 니 다.제거 할 수 있 으 면 "YES" 를 출력 하고, 그렇지 않 으 면 "NO" 를 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    YES
NO
NO
NO
NO
YES
   
   
   
   

 
근 데 이 문 제 는 판단 이 참 길 어 요.시간 초과 가능성 도 예고 하고 있다.근 데 제 코드 는 7000 MS 에 가 까 워 요.
말 이 많 지 않 습 니 다. 표준 DFS 는 간단 한 문제 라 고 할 수 있 습 니 다.
코드 를 보십시오:

#include <stdio.h>
#include <string.h>
#define MAX 1010
int dir[4][2] = {1,0,-1,0,0,1,0,-1} ;
struct Point{
	int x , y;
} ;

int visited[MAX][MAX] ,map[MAX][MAX];
int n , m; //    
Point des ;		//     

bool judge(Point p)
{
	if(p.x>n || p.x<=0 || p.y>m ||p.y<=0)
	{
		return false ;
	}
	return true ;
}

bool DFS(Point now , int direction , int count)
{
	if(count==3)
	{
		return false ;
	}
	else
	{
		for(int i = 0 ; i < 4 ; ++i)
		{
			Point next;
			next.x = now.x+dir[i][0] ;
			next.y = now.y+dir[i][1] ; 
			int flag = 0 ;
			if(direction != i && direction != -1)  //       ，     
			{
				flag = 1 ;
			} 
			if(visited[next.x][next.y])
			{
				continue ;
			}
			if(map[next.x][next.y] != 0)
			{
				if(next.x==des.x && next.y == des.y && count+flag<3)
				{
					return true ;
				}
				continue ;
			}
			if(judge(next))
			{
				visited[next.x][next.y] = true ;
				if(DFS(next,i,count+flag))
				{
					return true ;
				}
				visited[next.x][next.y] = false ;
			}
		}
	}
	return false ;
}
int main()
{
	while(scanf("%d%d",&n,&m)!= EOF && (n||m))
	{
		for(int i = 1 ; i <= n ; ++i)
		{
			for(int j = 1 ; j <= m ; ++j)
			{
				scanf("%d",&map[i][j]) ;
			}
		}
		int q ;
		scanf("%d",&q);
		for(int i = 0 ; i < q ; ++i)
		{
			Point p1;
			scanf("%d%d%d%d",&p1.x,&p1.y,&des.x,&des.y) ;
			//   
			if(map[p1.x][p1.y] != map[des.x][des.y])
			{
				printf("NO
");
				continue ;
			}
			else if(map[p1.x][p1.y] == 0)
			{
				printf("NO
");
				continue ;
			}
			memset(visited,0,sizeof(visited)) ;
			if(DFS(p1,-1,0))
			{
				printf("YES
");
			}
			else
			{
				printf("NO
") ;
			}
		}
	}
	return 0 ;
}