POJ 3009 圖的遍歷+DFS+回溯

【題意簡述】：大概的意思就是冰壺滑行，給你一個出發的點，一個終點，只能向四個方向滑行，如果碰到那個什麼東西，就把它打碎！然後繼續滑行！直至走到終點，問你走的最少的步數是多少，如果不能走就輸出-1，如果走的步數超過10步也輸出-1！詳細內容：http://poj.org/problem?id=3009

【思路】：又一道，深度優先搜索+回溯的問題！這個要多積累！！多回顧！

我想既然是搜索的問題就是Step By Step ，一步一步的思考，解決處理這個問題！也需要經驗的積累！

詳細的想法，看代碼吧！

//240K 219Ms
/*
	這裡的思路（順序！）過程很重要，我們要先判斷是否滿足臨界條件，然後讓冰壺滑動， 
	然後再 對是否撞碎那個面進行調整！！ 
*/
 
#include
#include
#include 
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=0&&ny=0&&maps[nx][ny] != 1) //可以繼續向前滑！
		{
			if(nx == ex&&ny == ey)
			{
				if(step+1=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>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;
}