本文主要是介绍POJ 3009，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3009
题目大意：在一个矩形游戏盘上，有石头，冰球，终点，起点。规则：上下左右抛出冰球，且抛出后除非碰到石头或终点，否则不停止。如果出界或者连续抛出10次以上就算失败。另外，冰球不能从紧挨着石头的一方抛出；一旦冰球碰到石头，则立即停止，石头消失，然后可以进行下一次抛出。
题目的思路是深度优先遍历，但是做了两晚也没做出来，参考网上的AC代码后，发现自己的思路是有问题。总结如下：
1. 一个最致命的问题是两个函数的返回值所表达的意思是相同的，这一定预示着程序的失败。
2. 搜索的深度就是抛出的次数。
代码如下：
<span style="font-size:18px;">#include<stdio.h>
const int HMAX = 25;
const int WMAX = 25;
int res;
int graph[HMAX][WMAX];
int W, H, istart, jstart;
int hoff[4] = { -1, 1, 0 , 0};
int woff[4] = { 0, 0, -1, 1};
void init(){
<span style="white-space:pre"> </span>res = 2000;
<span style="white-space:pre"> </span>scanf("%d%d", &W, &H);
<span style="white-space:pre"> </span>for(int i = 0; i < H; i++){
<span style="white-space:pre"> </span>for(int j = 0; j < W; j++){
<span style="white-space:pre"> </span>scanf("%d", &graph[i][j]);
<span style="white-space:pre"> </span>if(graph[i][j] == 2){
<span style="white-space:pre"> </span>istart = i;
<span style="white-space:pre"> </span>jstart = j;
<span style="white-space:pre"> </span>graph[i][j] = 0;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>return ;
}
void minFindGoal(int is, int js, int depth){
<span style="white-space:pre"> </span>if( depth > 10 || depth >= res ) return; //剪枝：减掉与现有结果相同或者更大的可能情况，效果：从163ms到63ms
<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>for(int k = 0; k < 4; k++){
<span style="white-space:pre"> </span>if( graph[is+hoff[k]][js+woff[k]] == 1 ) continue;
<span style="white-space:pre"> </span>int i, j;
<span style="white-space:pre"> </span>for( i = is + hoff[k], j = js + woff[k]; 0 <= i && i < H && 0 <= j && j < W && graph[i][j] == 0; i += hoff[k], j += woff[k] ){;}
<span style="white-space:pre"> </span>if( i < 0 || i >= H || j < 0 || j>= W ){
<span style="white-space:pre"> </span>continue;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>if(graph[i][j] == 3){
<span style="white-space:pre"> </span>res = res < depth ? res: depth;
<span style="white-space:pre"> </span>break; //剪枝：如果找到，其余方向只能是大于等于它
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>graph[i][j] = 0;
<span style="white-space:pre"> </span>minFindGoal(i-hoff[k], j-woff[k], depth + 1);
<span style="white-space:pre"> </span>graph[i][j] = 1;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>return;
}
int main()
{
<span style="white-space:pre"> </span>while(1){
<span style="white-space:pre"> </span>init();
<span style="white-space:pre"> </span>if( W == 0 && H == 0 ) break;
<span style="white-space:pre"> </span>minFindGoal(istart, jstart, 1);
<span style="white-space:pre"> </span>if( res < 2000 )
<span style="white-space:pre"> </span>printf("%d\n", res);
<span style="white-space:pre"> </span>else
<span style="white-space:pre"> </span>printf("%d\n", -1);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>return 0;
}</span>这篇关于POJ 3009的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
