hdoj1010

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1010
这道题作为我初学dfs,记一下,虽然很早就看过dfs算法,但是一直没用它做过题,感觉对它的认识停留在表面。所以接下来要多做搜索题。
先记录些本菜鸟的体会:
1.基于dfs的遍历(如图的dfs遍历),也就是访问完一个节点(指对该点相邻状态均已dfs)回溯到搜索树的上一层时,如果不将该节点改回未访问,则只能遍历所有状态仅一次。
2.要尝试所有路径,则必须在回溯时,重新修改访问情况(修改visit数组)
3.在dfs时,可以为dfs增加全局变量depth来记录当前dfs深度(反映到具体的迷宫问题中,就是走了几步)
4.dfs解决的是从起始状态到目标状态是否有可达路径,路径是什么
5.bfs则解决从起始状态到目标状态最短路径是什么
对于这道题,首先确定要用dfs。用bfs是思想性错误,因为题目要求是在t秒时正好到达出口(因为出口只在t秒时打开)
下面是代码:(注意:1.要剪枝;2.我的程序在所有状态之外加了一层初始化为已访问的状态,这样就不必判边界了,并且墙壁也可以看成已访问的状态,不用分离出来特意判断)

#include<stdio.h>
#include<stdlib.h>
bool visit[8][8];
char maze[8][8];
int depth=-1;
int a[5],b[5];
bool flag;
void dfs(int x,int y,int t)
{
	int i;
	visit[x][y]=true;
	depth++;
	if(maze[x][y]=='D'  && depth==t) {flag=true;return;}//开始没有加return,找到答案后仍然向下搜索,直到遍历整个状态空间(也就是整个迷宫)。结果984MS,改了之后406MS
	for(i=1;i<=4;i++)
	{
		if(visit[x+a[i]][y+b[i]]==false && !flag)//该点四周有未访问的点且现在未找到答案,则递归访问。
			dfs(x+a[i],y+b[i],t);
		else if(flag)//已经找到答案,不用再尝试其他方向,不断向前回溯,此时visit标志没有改回false,也就是说符合答案的路径各点标为了true
			return;
	}
depth--;//程序执行到这里说明该点四周的点均已访问,无法继续遍历,而且未找到答案,此时该点重新标为false,回到上一层,尝试其他方向的点
visit[x][y]=false;
return;
}
int main()
{
	int n,m,t;
	a[1]=-1;b[1]=0;
	a[2]=0;b[2]=-1;
	a[3]=1;b[3]=0;
	a[4]=0;b[4]=1;
	scanf("%d%d%d",&n,&m,&t);
	while(n!=0||m!=0||t!=0)
	{
		getchar();
		int beginx,beginy,endx,endy,i,j;
		flag=false;
		depth=-1;
		for(i=0;i<=n+1;i++)
			for(j=0;j<=m+1;j++)
				visit[i][j]=true;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&maze[i][j]);
				if(maze[i][j]=='S')
				{
					beginx=i;
					beginy=j;
				}
				if(maze[i][j]=='D')
				{
					endx=i;
					endy=j;
				}
				if(maze[i][j]!='X')
					visit[i][j]=false;
			}
			getchar();
		}
		if(((beginx+beginy)%2!=(endx+endy)%2)&&(t%2==0))
		{
			printf("NO\n");
			scanf("%d%d%d",&n,&m,&t);
			continue;
		}
		if(((beginx+beginy)%2==(endx+endy)%2)&&(t%2!=0))
		{
			printf("NO\n");
			scanf("%d%d%d",&n,&m,&t);
			continue;
		}
		dfs(beginx,beginy,t);
		if(flag==true)
			printf("YES\n");
		else
			printf("NO\n");
		scanf("%d%d%d",&n,&m,&t);
	}
return 0;
}

奇偶剪枝:如果起点横纵坐标和与终点坐标和奇偶性不同,则说明要走奇数步,如果要求走t步,t为偶数,则肯定不可能有答案;反之亦然。
开始没剪枝,果断TLE。。剪枝后984MS,进一步修改后406MS.

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>