POJ3009-Curling 2.0
题意：
要求把一个冰壶从起点“2”用最少的步数移动到终点“3”
其中0为移动区域，1为石头区域，冰壶一旦想着某个方向运动就不会停止，也不会改变方向（想想冰壶在冰上滑动），除非冰壶撞到石头1 或者 到达终点 3
如果能在10步以内到达终点，输出到达终点所需的步数，否则输出-1
注意的是：
冰壶撞到石头后，冰壶会停在石头前面，此时（静止状态）才允许改变冰壶的运动方向，而该块石头会破裂，石头所在的区域由1变为0. 也就是说，冰壶撞到石头后，并不会取代石头的位置。
终点是一个摩擦力很大的区域，冰壶若到达终点3，就会停止在终点的位置不再移动。
解题思路：
DFS，回溯，利用条件进行优良的剪枝来控制时间
以下代码会WA……想不破哎:-( 暂留
1 #include<iostream> 2 using namespace std; 3 const int maxn = 30; 4 int square[maxn][maxn]; 5 int w,h; 6 int r0,c0,r2,c2; 7 int bestp;///最优解 8 const int dh[4] = {-1,0,1,0};///向上0，右1，下2，左3 9 const int dw[4] = { 0,1,0,-1};10 11 bool inside(int x,int y)12 {13 ????return x>=1 && x <= h && y>=1 && y<=w;14 }15 16 bool walk(int x,int y,int dir,int &xx,int &yy)17 {///保证不滑到外面去18 ????///遇到墙面，需要改变square19 ????///到达终点，就停止20 ????///如果可行，需要改变当前的位置x,y21 ????int tempx = x+dh[dir];22 ????int tempy = y+dw[dir];23 ????///首先检测当前方位是否可以滑动24 ????if(inside(tempx,tempy) && square[tempx][tempy] == 1) return false;///第一步是墙面，不能滑动25 26 ????while(true)27 ????{28 ????????if(!inside(tempx,tempy)) return false;//滑倒了场外29 ????????if(square[tempx][tempy] == 3)//到达了终点30 ????????{31 ????????????xx = tempx;yy = tempy;32 ????????????return true;33 ????????}34 ????????if(square[tempx+dh[dir]][tempy+dw[dir]] == 1)///下一步滑到墙面35 ????????{36 ????????????xx = tempx;yy = tempy;37 ????????????square[tempx+dh[dir]][tempy+dw[dir]] = 0;///改变场地状态38 ????????????return true;39 ????????}40 ????????tempx+=dh[dir];tempy+=dw[dir];///划动一格41 ????}42 }43 void dfs(int x,int y,int deep)44 {45 46 ????///临界条件47 ????if(x==r2 && y==c2)48 ????{///寻找最优解49 ????????if(deep < bestp)50 ????????????bestp = deep;51 ????????return;52 ????}53 ????for(int i=0;i<=3;i++)54 ????{55 ????????int xx,yy;56 ????????bool flag = walk(x,y,i,xx,yy);57 ????????if(flag && deep<10)58 ????????????dfs(xx,yy,deep+1);59 ????????///回溯60 ????????if(flag && square[xx][yy] != 3)61 ????????{62 ????????????square[xx+dh[i]][yy+dw[i]] = 1;///改变场地状态63 ????????}64 65 ????}66 ????return;67 }68 69 int main()70 {71 ????while(cin>>w>>h && w && h)72 ????{73 ????????for(int i=1;i<=h;i++)///行74 ????????????for(int j=1;j<=w;j++)///列75 ????????????{76 ????????????????cin>>square[i][j];77 ????????????????if(square[i][j]==2)78 ????????????????{79 ????????????????????r0=i;c0=j;80 ????????????????????square[i][j]=0;81 ????????????????}82 ????????????????if(square[i][j]==3)83 ????????????????{84 ????????????????????r2=i;c2=j;85 ????????????????}86 ????????????}87 ????????bestp = 20;88 ????????dfs(r0,c0,0);89 ????????if(bestp>10)90 ????????{91 ????????????cout<<-1<<endl;92 ????????}93 ????????else94 ????????????cout<<bestp<<endl;95 ????}96 ????return 0;97 }POJ3009-Curling 2.0（WA）
原文地址：https://www.cnblogs.com/yxh-amysear/p/8454666.html