POJ 3009 图的遍历+DFS+回溯

【题意简述】：大概的意思就是冰壶滑行，给你一个出发的点，一个终点，只能向四个方向滑行，如果碰到那个什么东西，就把它打碎！然后继续滑行！直至走到终点，问你走的最少的步数是多少，如果不能走就输出-1，如果走的步数超过10步也输出-1！详细内容：http://poj.org/problem?id=3009

【思路】：又一道，深度优先搜索+回溯的问题！这个要多积累！！多回顾！

我想既然是搜索的问题就是Step By Step ，一步一步的思考，解决处理这个问题！也需要经验的积累！

详细的想法，看代码吧！

//240K 219Ms
/*
	这里的思路（顺序！）过程很重要，我们要先判断是否满足临界条件，然后让冰壶滑动， 
	然后再 对是否撞碎那个面进行调整！！ 
*/
 
#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;

int w,h;   //场地的宽和高
int sx,sy,ex,ey; //记录起点和终点的坐标 
int dx[4] = {0 ,0 ,-1 , 1};
int dy[4] = {1 ,-1 ,0 , 0};

int maps[20][20];//存放地图！ 
int best;//记录最优解！ 

void dfs(int bx,int by,int step)
{
	int nx,ny,i;
	if(step>best)  //剪枝，如果大于最优解，便直接返回！ 
		return;
	for(i = 0;i < 4;i++)
	{
		nx = bx + dx[i];
		ny = by + dy[i];
		if(nx >= h||nx < 0||ny >= w||ny <0||maps[nx][ny] == 1) // 越界或者有阻挡物 便剪枝！ 
			continue;
		while(nx<h&&nx>=0&&ny<w&&ny>=0&&maps[nx][ny] != 1) //可以继续向前滑！
		{
			if(nx == ex&&ny == ey)
			{
				if(step+1<best)
					best = step + 1;
				break;
			}
			nx += dx[i];//  没有阻碍或者越界情况，，便一直向前滑动！！ 
			ny += dy[i];
		}
		if(nx == ex&& ny ==ey)
			continue;
		if(nx <h&&nx>=0&&ny < w&&ny >=0)//保证在界内！ 
		{
			maps[nx][ny] = 0;
			dfs(nx -dx[i],ny - dy[i],step+1);
			maps[nx][ny] = 1;            //  !!!  这里是重点，还原阻挡物，回溯！！回溯是因为，
		 						         //这条路是你先试探性走的，你得知不可以走，所以才回溯，还原其本来的样貌，然后走其他的地方!
		} 
			 
	}
} 
int main()
{
	int i,j;
	while(scanf("%d%d",&w,&h),w||h)
	{
		best = 11;
		for(i=0;i<h;i++)           // 读入数据！！ 
			for(j=0;j<w;j++){
				cin>>maps[i][j];
				if(maps[i][j] == 2)
					sx = i,sy = j;
				if(maps[i][j] == 3)
					ex = i,ey = j;
			}
		dfs(sx,sy,0);         
		if(best <= 10)
			printf("%d\n",best);
		else
			printf("-1\n"); 
	}
	return 0;
}

POJ 3009 图的遍历+DFS+回溯,布布扣,bubuko.com

POJ 3009 图的遍历+DFS+回溯

原文：http://blog.csdn.net/u013749862/article/details/21878289