HDU 1728 미로 탈출 DFS + 태그 커 브 수 + 최적화

미궁 을 벗어나다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16764    Accepted Submission(s): 4086
Problem Description
주어진 m× n (m 행, n 열) 의 미로, 미로 에는 두 개의 위치 가 있 습 니 다. gloria 는 미궁의 한 위치 에서 다른 위치 로 가 고 싶 습 니 다. 물론 미로 중 일 부 는 공 터 이 고 gloria 는 통과 할 수 있 습 니 다. 어떤 곳 은 장애 입 니 다. 그녀 는 돌아 가 야 합 니 다. 미궁의 한 위치 에서 그 와 인접 한 4 개의 위치 까지 만 갈 수 있 습 니 다. 물론 걷 는 과정 에서 gloria 는 미로 밖으로 나 갈 수 없습니다.골 치 아 픈 것 은 글로 리 아 는 방향 감각 이 별로 없 는 사람 이기 때문에 그녀 는 걷 는 과정 에서 너무 많이 구 부 러 져 서 는 안 된다. 그렇지 않 으 면 그녀 는 쓰 러 질 것 이다.우 리 는 주어진 두 위치 가 모두 공 터 라 고 가정 합 니 다. 처음에 gloria 가 향 하 는 방향 은 정 해 지지 않 았 습 니 다. 그녀 는 네 방향 중 하 나 를 선택 하여 출발 할 수 있 습 니 다. 한 번 의 커 브 가 아 닙 니 다.글로 리 아 는 한 자리 에서 다른 자리 로 갈 수 있 을까요?
 
Input
제1 행위 1 개 정수 t (1 ≤ t ≤ 100) 는 테스트 데이터 의 개 수 를 나타 내 고 다음은 t 조 테스트 데이터 이 며 각 조 테스트 데이터 중,
첫 번 째 행위 의 두 정수 m, n (1 ≤ m, n ≤ 100) 은 각각 미궁의 줄 수 와 열 수 를 나타 내 고, 다음 m 줄 은 n 개의 문 자 를 포함 하 며, 그 중 문자 '' 는 이 위 치 를 공 터 로 표시 하고, 문자 '*' 는 이 위 치 를 장애 로 표시 하 며, 입력 데이터 에는 이 두 가지 문자 만 있 으 며, 각 조 테스트 데이터 의 마지막 행위 5 개의 정수 k, x
1, y
1, x
2, y
2 (1 ≤ k ≤ 10, 1 ≤ x
1, x
2 ≤ n, 1 ≤ y
1, y
2 ≤ m), 그 중 k 는 gloria 가 가장 많이 돌 수 있 는 커 브 수 를 나타 낸다. (x
1, y
1),  (x
2, y
2) 두 자 리 를 나타 내 는 x
1，x
2 대응 열, y
1, y
2 대응 행.
 
Output
각 그룹의 테스트 데 이 터 는 한 줄 로 대응 합 니 다. 만약 gloria 가 한 위치 에서 다른 위치 로 갈 수 있다 면 "yes" 를 출력 합 니 다. 그렇지 않 으 면 "no" 를 출력 합 니 다.
 
Sample Input

 
   

     2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3 
   
 
  

 

标志转弯的确实难想到。一晚上的青春。

坑点：X，Y的输入是反的，注意读题。。还有就是只要后搜的转弯数大于前搜的话就剪。（不能等）

#include 
#define inf 0x3fffffff
#include 
#include 
using namespace std;
char map[105][105];  
int wan[105][105];  //   ，              
int dirx[4]={-1,0,1,0};
int diry[4]={0,1,0,-1};
int n,m,k,x2,y2;
int flag;
void dfs(int x,int y,int dir)
{
	int i;
	int ssx;
	int ssy;
	if( x==x2 &&y==y2)  //         
	{
		if(wan[x][y]<=k)  //      k。
			flag=true;  //    
		return;
	}
	if(wan[x][y]>k)
		return ;   //     K，     
	if(wan[x][y]==k &&x!=x2 &&y!=y2)
		return;   //       K，        。   
	for(i=0;i<4;i++)
	{
		ssx=x+dirx[i];
		ssy=y+diry[i];
		if(ssx<0 || ssy<0 ||ssx>=m ||ssy >=n)
			continue;//     
		if(map[ssx][ssy]=='*'||wan[x][y]>wan[ssx][ssy])
			continue;//     ，                    。（   ）
		if(dir!=-1 &&i!=dir &&wan[x][y]+1>wan[ssx][ssy])
			continue;//    ，                    （+1       ）
		wan[ssx][ssy]=wan[x][y];
		if(dir!=-1 &&dir!=i)  //     ，i     。
			wan[ssx][ssy]++; //       。
		dfs(ssx,ssy,i); //         。
		if(flag)
			return;
	}
}
int main()
{
	int t,i,j,x1,y1;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&m,&n);
		for(i=0;i