本文主要是介绍POJ 3009 Curling 2.0 (DFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3009
题意：类似冰壶比赛。在一个矩阵中有一个起点一个终点，有空地和障碍物。从起点开始可以使冰壶朝一个方向运动（如果该方向没有障碍物的话）直到撞到障碍或者飞出边界或者到达终点，飞出边界游戏失败，撞到障碍障碍消失，冰壶停在障碍前，可以使得冰壶再次运动，问能不能在十次（包括）操作之内使得冰壶到达终点，不能则输出-1。能则输出最少的操作次数。
题解：DFS。只不过在DFS的时候的状态转移并不是相邻的一个格子，而是上下左右四条直线。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=25;
int a[MAX][MAX];
int w,h;
int step,minstep;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int sx=0,sy=0;
void dfs(int x,int y,int step)
{if(step>10) return ;//cout<<x<<" "<<y<<" "<<step<<endl;for(int i=0;i<4;i++){for(int j=1;;j++){int nx=x+j*dx[i];int ny=y+j*dy[i];if(a[nx][ny]==3) {minstep=min(minstep,step);return ;}if(nx<0||nx>=h||ny<0||ny>=w){break;}if(a[nx][ny]==1){if(j==1) break;else {a[nx][ny]=0;dfs(nx-dx[i],ny-dy[i],step+1);a[nx][ny]=1;break;}}}}return ;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d",&w,&h)){memset(a,0,sizeof(a));if(w==0&&h==0) break;step=0;minstep=12;for(int i=0;i<h;i++){for(int j=0;j<w;j++){scanf("%d",&a[i][j]);if(a[i][j]==2) {sx=i;sy=j;}}}dfs(sx,sy,1);if(minstep>10) printf("-1\n");else printf("%d\n",minstep);}return 0;
}这篇关于POJ 3009 Curling 2.0 (DFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
