POJ3009-Curling 2.0

题意：

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

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

如果能在10步以内到达终点，输出到达终点所需的步数，否则输出-1

注意的是：

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

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

解题思路：

DFS，回溯，利用条件进行优良的剪枝来控制时间

以下代码会WA……想不破哎:-( 暂留

 #include<iostream>

 using namespace std;

 const int maxn = ;

 int square[maxn][maxn];

 int w,h;

 int r0,c0,r2,c2;

 int bestp;///最优解

 const int dh[] = {-,,,};///向上0，右1，下2，左3

 const int dw[] = { ,,,-};

 bool inside(int x,int y)

 {

     return x>= && x <= h && y>= && y<=w;

 }

 bool walk(int x,int y,int dir,int &xx,int &yy)

 {///保证不滑到外面去

     ///遇到墙面，需要改变square

     ///到达终点，就停止

     ///如果可行，需要改变当前的位置x,y

     int tempx = x+dh[dir];

     int tempy = y+dw[dir];

     ///首先检测当前方位是否可以滑动

     if(inside(tempx,tempy) && square[tempx][tempy] == ) return false;///第一步是墙面，不能滑动

     while(true)

     {

         if(!inside(tempx,tempy)) return false;//滑倒了场外

         if(square[tempx][tempy] == )//到达了终点

         {

             xx = tempx;yy = tempy;

             return true;

         }

         if(square[tempx+dh[dir]][tempy+dw[dir]] == )///下一步滑到墙面

         {

             xx = tempx;yy = tempy;

             square[tempx+dh[dir]][tempy+dw[dir]] = ;///改变场地状态

             return true;

         }

         tempx+=dh[dir];tempy+=dw[dir];///划动一格

     }

 }

 void dfs(int x,int y,int deep)

 {

     ///临界条件

     if(x==r2 && y==c2)

     {///寻找最优解

         if(deep < bestp)

             bestp = deep;

         return;

     }

     for(int i=;i<=;i++)

     {

         int xx,yy;

         bool flag = walk(x,y,i,xx,yy);

         if(flag && deep<)

             dfs(xx,yy,deep+);

         ///回溯

         if(flag && square[xx][yy] != )

         {

             square[xx+dh[i]][yy+dw[i]] = ;///改变场地状态

         }

     }

     return;

 }

 int main()

 {

     while(cin>>w>>h && w && h)

     {

         for(int i=;i<=h;i++)///行

             for(int j=;j<=w;j++)///列

             {

                 cin>>square[i][j];

                 if(square[i][j]==)

                 {

                     r0=i;c0=j;

                     square[i][j]=;

                 }

                 if(square[i][j]==)

                 {

                     r2=i;c2=j;

                 }

             }

         bestp = ;

         dfs(r0,c0,);

         if(bestp>)

         {

             cout<<-<<endl;

         }

         else

             cout<<bestp<<endl;

     }

     return ;

 }

巴特西

POJ3009-Curling 2.0（WA）

POJ3009-Curling 2.0

最新文章

热门文章