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是個沒什麼方向感的人，是以，她在行走過程中，不能轉太多彎了，否則她會暈倒的。我們假定給定的兩個位置都是空地，初始時，gloria所面向的方向未定，她可以選擇4個方向的任何一個出發，而不算成一次轉彎。gloria能從一個位置走到另外一個位置嗎？  

Input 　　第1行為一個整數t (1 ≤ t ≤ 100),表示測試資料的個數，接下來為t組測試資料，每組測試資料中，

　　第1行為兩個整數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
        

Sample Output

no
yes
        

Source “網新恩普杯”杭州電子科技大學程式設計邀請賽

标志轉彎的确實難想到。一晚上的青春。

坑點：X，Y的輸入是反的，注意讀題。。還有就是隻要後搜的轉彎數大于前搜的話就剪。（不能等）

#include <stdio.h>
#define inf 0x3fffffff
#include <string.h>
#include <algorithm>
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<m;i++)
			scanf("%s",map[i]);
		scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
		y1--;x1--;y2--;x2--;//  題目從1開始，我從0開始
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				wan[i][j]=inf;//  一開轉彎數全部初始為無窮大
			wan[x1][y1]=0;//  開始點為0
			flag=false;
			dfs(x1,y1,-1);//  -1進去，表示第一次不轉彎
			if(flag)  
				printf("yes\n");
			else
				printf("no\n");
	}
	return 0;
}