poj 3009 Curling 2.0 (dfs)

2021-07-15 14:04

阅读：534

链接:poj 3009

题意：在一个冰面网格板上，有空白处（无障碍），和障碍块。有一个小石头，给定其起点和终点。求从起点到终点的最小步数

规则：小石头不能在障碍区运动，一旦从某一方向開始运动，不会改变方向，也不会停止。除非碰到障碍物或到达终点才会停止，这为一步。若碰到障碍物。小石头将停在障碍物的旁边，被碰到的一个障碍物将消失。

输入：1代表障碍物（不可到达），0代表空白区，2,代表起点。3代表终点

输出：若小石头能到达终点，且步数最多为十步，输出最小步数，否则输出-1.

思路：dfs+回溯

要确定小石头是运动还是精巧状态，若为精巧，旁边为障碍区。是不能走的。而且当開始小石头运动，到接下来第一次停止为一步，期间方向没改变。仅仅有停止后才干改变运动方向，因此dfs时要确定小石头的运动状态和方向.

剪枝：由于步数不能超过10，能够以此作为剪枝条件

#include
int m,n,a[21][21],min;
int x[4]={-1,1,0,0},y[4]={0,0,-1,1};
void dfs(int i,int j,int step,int dir,int sta,int flag) 
{                      //step表示当前步数，dir运动方向。sta运动状态，flag是否消除障碍
    int k,r,c;
    if(step>10)         //剪枝，步数不能超过10
        return ;
    if(a[i][j]==3){        //到达终点，若步数比最小步数小，更新最小步数
        if(step=1&&r=1&&c=1&&r=1&&c

上一篇：PYTHON语言之常用内置函数

下一篇：Redis 通信协议

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：poj 3009 Curling 2.0 (dfs)
文章链接：http://soscw.com/index.php/essay/105595.html

亲，登录后才可以留言！

poj 3009 Curling 2.0 (dfs)

评论

热门文章

推荐文章

最新文章

置顶文章