【 hdoj 1010 】 뼈의 유혹 (미로 + 가지치기)

제목:http://acm.hdu.edu.cn/showproblem.php?pid=1010
제목: 미로 (출발점 과 종점 포함) 를 제시 하고 경 로 를 찾 아야 합 니 다. 이 경로 의 길 이 는 반드시 특정한 길이 여야 합 니 다.
본 문 제 를 풀 기 전에 미로 문 제 를 배 웠 습 니 다.http://blog.csdn.net/ten_sory/article/details/66975811
미로 문 제 를 이해 하 는 토대 에서 본 문 제 를 푸 세 요. 본 문제 의 난점 은 바로 가지치기 문제 입 니 다. 일반적인 DFS + 역 추적 방법 으로 만 이 문 제 를 풀 면 시간 을 초과 할 수 있 기 때문에 가지치기 기술 이 필요 합 니 다.
1. 패 리 티 가지치기: 현재 위치 가 (x, y) 이 고 종점 이 (dx, dy) 이 라면 T 단계 에서 (x, y) (dx, dy) 로 가 야 합 니 다. 가지치기 란 T 단계 에서 (x, y) 를 완성 할 가능성 을 확인 하 는 것 입 니 다. (x, y) - > (dx, dy) 의 가장 적은 절 차 는 abs (dx - x) + abs (dy - y) 입 니 다. 다음 그림 은 두 점 사이 의 맨 해 튼 거리 입 니 다.

물론 이 최 단 거리 (path 1 로 설정) 가 반드시 통 하 는 것 은 아니 므 로 다른 경로 가 존재 합 니 다. 분명 한 것 은 다른 임의의 경로 (path 2 로 설정) 의 길 이 는 path 1 의 길이 의 패 리 티 와 같 습 니 다. path 1 과 path 2 의 출발점 과 종점 은 종축 에서 반드시 같 기 때 문 입 니 다. path 2 가 종축 에서 한 걸음 더 걸 었 다 면 반드시 종축 에서 한 걸음 더 걸 어야 합 니 다.오직 이렇게 해야만 종점 에 도착 할 수 있다. 마찬가지 로 횡축 도 마찬가지다.
이 결론 에 따 르 면 (x, y) 에서 (dx, dy) 까지 의 가장 짧 은 경로 의 길이 (걸음 수) 는 반드시 규정된 걸음 수의 패 리 티 와 같 습 니 다. 패 리 티 가 다 르 면 이 경로 의 탐 사 를 중지 합 니 다.
2. 작은 가지치기: 만약 에 규정된 시간 이 T 이 고 장애물 의 개 수 는 wall 개 라면 n * m - wall = 걸 을 수 있 는 점 의 개수 < = T 라면 특정한 실행 가능 한 경로 의 길이 가 T 가 존재 하지 않 고 종료 하면 됩 니 다.
코드 는 다음 과 같 습 니 다:

#include
using namespace std;

int flag;
char maze[10][10];
int vis[10][10];
int n,m,T,t;
int sx,sy,dx,dy;

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};//4   

int abs(int x){return x>0?x:(-x);}

void dfs(int x,int y,int t)
{
	if(x==dx && y==dy && t==T)//    
	{
		flag = 1;
		return;
	}
	if(x<0 || x>=n || y<0 || y>=m)//  
		return;

	/*    */
	int temp1 = abs(dx-x) + abs(dy-y);
	int temp2 = abs(T-t);//    
	int temp = abs(temp1-temp2);
	if(temp%2!=0)
		return;

	//     (x,y)     ，  , , , 4     
	for(int i=0;i<4;i++)
	{
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];//     (nx,ny)

		if(0<=nx && nx> maze[i];
			for(int j=0;j

재 귀 와 역 추적 법 에 대한 설명
재 귀 + 역 추적 법 에서 만약 에 하나의 탐측 return 이 끝나 면 이번 재 귀 가 끝 난 후에 역 추적 하여 다음 재 귀 를 진행 합 니 다. 그래서 특정한 재 귀 의 return 은 전체 재 귀 함수 의 return 을 대표 하지 않 습 니 다.
이 문제 에서 특정한 재 귀 에서 요구 에 부합 되 는 경 로 를 찾 으 면 전체 함 수 를 끝 냅 니 다. 이번 재 귀 를 끝 내 는 것 만 이 아 닙 니 다.
따라서 본 문 제 는 거 슬러 올 라 가기 전에 요구 에 부합 되 는 경 로 를 찾 았 는 지 판단 해 야 한다. 즉, dfs (...) 이후 에 즉시 if (flag) 를 판단 해 야 한다.  return;
본 논문 의 가지치기 전략 참고:http://www.cnblogs.com/grubbyskyer/p/3855533.html