题目链接：

/**************************************/

懒得写题意，下面是抄自小优师姐的题意解释：

就是要求把一个冰壶从起点“2”用最少的步数移动到终点“3”

其中0为移动区域，1为石头区域，冰壶一旦想着某个方向运动就不会停止，也不会改变方向（想想冰壶在冰上滑动），除非冰壶撞到石头1 或者 到达终点 3

注意的是：

冰壶撞到石头后，冰壶会停在石头前面，此时（静止状态）才允许改变冰壶的运动方向，而该块石头会破裂，石头所在的区域由1变为0. 也就是说，冰壶撞到石头后，并不会取代石头的位置。

终点是一个摩擦力很大的区域，冰壶若到达终点3，就会停止在终点的位置不再移动。

/**************************************/

 

这一题还是搜索题，但是要注意每一次搜索下一步时board都会变化，所以用bfs确实没办法。用dfs时又要考虑时间的问题。所以要剪枝，题目也告诉我们超过十步就是失败。

做这道题用了两天时间，是不断的WA，不断的找错。在这个过程中发现自己写代码还是太急于写，不是每一步都很严谨。

好了，贴出来终于AC的代码:

1 ///2014.3.28 - 2014.3.30  2 ///poj3009  3   4 #include 
     
        5 #include 
      
         6 using namespace std;  7   8 struct position{  9     int h,w; 10 }; 11  12 int H,W;  ///the height and width of the board 13 int board[25][25]; 14 int S_h,S_w,E_h,E_w;   ///S_h:the height of the start; E:end; 15 int minstep; 16  17 const int addH[4] = {-1,0,1,0};    ///for easy to go next position 18 const int addW[4] = {
   0,-1,0,1}; 19  20 void init(){ 21     for(int i=1 ; i<=H ; i++){ 22         for(int j=1 ; j<=W ; j++){ 23             cin>>board[i][j]; 24             if( board[i][j]==2 ){ 25                 S_h = i; 26                 S_w = j; 27                 board[i][j] = 0;   ///set 0 to the start place after record it 28             } 29             if( board[i][j]==3 ){ 30                 E_h = i; 31                 E_w = j; 32             } 33         } 34     } 35     minstep = 11; 36 } 37  38 position findNextPosition(position pos,int direction){ 39     while( board[ pos.h+addH[direction] ][ pos.w+addW[direction] ]==0 &&  40             pos.h+addH[direction]>=1 && pos.h+addH[direction]<=H &&  41             pos.w+addW[direction]>=1 && pos.w+addW[direction]<=W ){ 42         pos.h += addH[direction]; 43         pos.w += addW[direction]; 44     } 45     if( board[ pos.h+addH[direction] ][ pos.w+addW[direction] ] == 3 && 46             pos.h+addH[direction]>=1 && pos.h+addH[direction]<=H &&  47             pos.w+addW[direction]>=1 && pos.w+addW[direction]<=W ){ 48         pos.h += addH[direction]; 49         pos.w += addW[direction]; 50         return pos; 51     } 52     else if( board[ pos.h+addH[direction] ][ pos.w+addW[direction] ] == 1 && 53             pos.h+addH[direction]>=1 && pos.h+addH[direction]<=H &&  54             pos.w+addW[direction]>=1 && pos.w+addW[direction]<=W ){ 55         return pos; 56     } 57     else{ 58         pos.h = -1; 59         pos.w = -1; 60         return pos; 61     } 62 } 63  64 void dfs(int h,int w,int step){ 65     if( step>10 )  ///pruning 66         return; 67  68     if( h==E_h && w==E_w ){ 69         if( step
       
        >W>>H && H && W ){ 99         init();100 101         dfs(S_h,S_w,0);102         if( minstep<11 )103             cout<
        
         <