poj 3009 Curling 2.0 DFS

/*

 

题目:

    冰球游戏,每次都得需要往左右前后移动相应的步数,只有遇到石块才会停止在石块前,不然的话

    就要出界。问如何从出发点移动冰球使它到达终点,若不能输出-1,可以的话输出最小的移动次数。

    另外超出十次还没移动到终点的话,也算输

 

分析:

    由于长和宽都最大只有20,另外也同样只有十次而已,所以可以用深搜来做。每次先判断需要移动的

    到哪个位置,然后判断到达终点时的总移动次数是否大于10,没有则更新答案。另外需要注意的是,

    每次移动时都需要先对该位置碰到的石块置空,然后递归搜索该位置是否能到达终点,递归完了之后

    需要对地图位置置为1,代表原来的位置为石块。

   

 

*/

#include <iostream>

#include <cstring>

#include <cstring>

using namespace std;

#define MAXN 22

int map[MAXN][MAXN],n,m;

bool use[MAXN][MAXN];

#define INF 1000000  //无限大

struct node{  //二维位置

    int x,y;

}s,e;

int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};  //位移偏移量

int ans;

node move(int x,int y,int d){   //计算需要移动到的地方,返回该位置

    node cur;

    cur.x = cur.y = -1;  //返回cur,若cur.x==-1,表示不能往这个方向移动

    while(1){

       x += dir[d][0];

       y += dir[d][1];

       if(x<1||y<1||x>n||y>m)   //判断是否越界

           return cur;

       if(map[x][y]==1){    //此处为石块,应移动到石块前

           cur.x = x-dir[d][0];

           cur.y = y-dir[d][1];

           return cur;       //返回前一处位置

       }

       else if(map[x][y]==3){   //此处为终点

           return e;

       }

    }

    return cur;

}

void dfs(node cur,int x){

    node temp;

    if(x>9)    //次数大于9次时,不行

       return;

    for(int i=0;i<4;i++){

       temp = move(cur.x,cur.y,i);

       if(temp.x==-1)    //不能移动

           continue;

       if(temp.x==e.x&&temp.y==e.y)    //是终点的话

       {

           ans = min(ans,x); //更新答案

           return;

       }

       if(temp.x==cur.x&&temp.y==cur.y)   //若往这一方向不能移动一步(卡住了)

           continue;

       map[temp.x+dir[i][0]][temp.y+dir[i][1]] = 0;//取反

       dfs(temp,x+1);    //递归该位置

       map[temp.x+dir[i][0]][temp.y+dir[i][1]] = 1;//取反

    }

}

int main()

{

    freopen("sum.in","r",stdin);

    freopen("sum.out","w",stdout);

    while(cin>>m>>n,n||m){

       ans = 1000000;

       memset(use,false,sizeof(use));

       for(int i=1;i<=n;i++){

           for(int j=1;j<=m;j++){

              scanf("%d",&map[i][j]);

              if(map[i][j]==2){

                  s.x = i;

                  s.y = j;

              }

              else if(map[i][j]==3){

                  e.x = i;

                  e.y = j;

              }

           }

       }

       dfs(s,0);

       if(ans==INF)

           cout<<-1<<endl;

       else

           cout<<ans+1<<endl;

    }

 

    return 0;

}

原文地址:https://www.cnblogs.com/yejinru/p/2471760.html