本文主要是介绍POJ3009 Curling 2.0【DFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://poj.org/problem?id=3009
题目大意：
一种在宽为M高为N大小的矩阵上玩的冰壶游戏，起点字符为'2'，终点字符为'3'，矩阵上'0'为可移动区域，
'1'为石头区域。冰壶刚开始是静止的，每走一步都会选择某个方向运动，而且会沿着该方向一直运动不停，
也不会改变方向，除非冰壶碰到石头或者到达终点，才会停下(这算一步)。冰壶在运动的时候，不能改变方
向。冰壶碰到石头会变成静止状态，这时候石头会破裂，该区域变为可移动区域，而冰壶就可以改变方向了。
冰壶一旦走到终点就不再移动。问：冰壶从起点到终点最少停多少次(走多少步)？
思路：
1)记录起点和终点位置，并将起点和终点标为可移动区域。
2)因为需要找到所有通路中的最短步数，所以用DFS寻找从起点到终点的最短步数。
3)每走一步到静止之后，可选择四个方向，DFS继续下一步。
4)在撞到石头破裂后需要继续下一步，这时候需要回溯回来重新选择方向。
5)冰壶不可以出界。
6)不能超过10步。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;int vis[25][25];
int N,M;
int flag,SumStep;
int Sx,Sy,Ex,Ey;
int Dire[4][2] = {0,1,0,-1,1,0,-1,0};void DFS(int x,int y,int step)
{int tx,ty;if(step >= 10) //超过10步算失败return ;for(int i = 0; i < 4; i++){if(!vis[x+Dire[i][0]][y+Dire[i][1]]) //选择可移动的方向{tx = x;ty = y;while(!vis[tx+Dire[i][0]][ty+Dire[i][1]]) //移动到障碍点或是边界点前{tx = tx + Dire[i][0];ty = ty + Dire[i][1];if(tx == Ex && ty == Ey){if(SumStep > step+1) //找到路径SumStep = step+1;flag = 1;return ;}if(tx < 0 || tx >= N || ty < 0 || ty >= M) //判断越界break;}if(tx >= 0 && tx < N && ty >= 0 && ty < M && step+1 < 10) //撞上障碍后{vis[tx+Dire[i][0]][ty+Dire[i][1]] = 0; //石头破裂，变为可移动区域DFS(tx,ty,step+1); //选择方向，继续移动vis[tx+Dire[i][0]][ty+Dire[i][1]] = 1; //回溯回来，继续选择上一步方向}}}
}int main()
{while(~scanf("%d%d",&M,&N) && (M||N)){memset(vis,0,sizeof(vis)); for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){scanf("%d",&vis[i][j]);if(vis[i][j] == 2) //记录起点位置{Sx = i;Sy = j;vis[i][j] = 0;}if(vis[i][j] == 3) //记录终点位置{Ex = i;Ey = j;vis[i][j] = 0;}}}flag = 0;SumStep = 0xffffff0;DFS(Sx,Sy,0);if(!flag)SumStep = -1;printf("%d\n",SumStep);}return 0;
}
这篇关于POJ3009 Curling 2.0【DFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
