poj 3009 Curling 2.0 (dfs)
2021-07-15 14:04
阅读:546
题意:在一个冰面网格板上,有空白处(无障碍),和障碍块。有一个小石头,给定其起点和终点。求从起点到终点的最小步数
规则:小石头不能在障碍区运动,一旦从某一方向開始运动,不会改变方向,也不会停止。除非碰到障碍物或到达终点才会停止,这为一步。若碰到障碍物。小石头将停在障碍物的旁边,被碰到的一个障碍物将消失。
输入:1代表障碍物(不可到达),0代表空白区,2,代表起点。3代表终点
输出:若小石头能到达终点,且步数最多为十步,输出最小步数,否则输出-1.
思路:dfs+回溯
要确定小石头是运动还是精巧状态,若为精巧,旁边为障碍区。是不能走的。而且当開始小石头运动,到接下来第一次停止为一步,期间方向没改变。仅仅有停止后才干改变运动方向,因此dfs时要确定小石头的运动状态和方向.
剪枝:由于步数不能超过10,能够以此作为剪枝条件
#includeint 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 通信协议
评论
亲,登录后才可以留言!