POJ3009-Curling2.0

题意总结如下:

2表示冰球的起点 3表示冰球的终点 1表示有障碍物.当冰球碰上障碍物时,障碍物会破碎.冰球停在前一格. 0 表示可以通行,无阻力,所以冰球在这上面会一直滑行

由于场地的模型中,障碍物会被击毁,所以不能用普通的宽搜,这里用深搜 加上回朔解决.

//bnu3128
#include<stdio.h>
#include<string.h>
#define MAX 25
#define INF 100
int mmp[MAX][MAX];
int w,h,ans;
int si,sj,ei,ej;
int dir[4][2]={-1,0,0,1,1,0,0,-1};

//检查是否越界
bool check(int a,int b)
{
    if(a<h && b<w && a>=0 && b>=0)
        return true;
    return false;
}
int min(int a,int b)
{
    return a<b?a:b;
}
//深搜加回朔
void dfs(int a,int b,int step)
{
    if(step>10)//当步骤大于10时,退出
        return ;
    int a1=a,b1=b;
    for(int  i=0;i<4;i++)
    {
        a1=a+dir[i][0];
        b1=b+dir[i][1];
        if(mmp[a1][b1]==1)//下一个点有球挡住了,无法通行
            continue;
        //尝试找到下一个静止点,模拟冰球的运动
        while(!mmp[a1][b1] && check(a1,b1))
        {
            a1=a1+dir[i][0];
            b1=b1+dir[i][1];
        }
        if(check(a1,b1))
        {//当没有越界时
            if(mmp[a1][b1]==1)
            {//如果遇上了其他的球
                mmp[a1][b1]=0;//击碎这个球
                dfs(a1-dir[i][0],b1-dir[i][1],step+1);
                mmp[a1][b1]=1;//回朔法,恢复场地的状态
            }
            else if(mmp[a1][b1]==3)
            {//到达终点,取最小的值
                ans=min(ans,step+1);
            }
        }
    }
}
int main()
{
    int i,j;
    while(1)
    {
        scanf("%d%d",&w,&h);
        if(w==0 || h==0) break;
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                scanf("%d",&mmp[i][j]);
                if(mmp[i][j]==2)
                {
                    si=i;
                    sj=j;
                    mmp[i][j]=0;
                }
                if(mmp[i][j]==3)
                {
                    ei=i;
                    ej=j;
                }
            }
        }
        ans=INF;
        dfs(si,sj,0);
        if(ans<=10)
            printf("%d\n",ans);
        else
            printf("-1\n");
    }
    return 0;
}