poj 3009 curling2.0 (dfs)

浏览数：27 / 时间：2015年06月09日

题意：一幅冰壶游戏地图中有起点，终点，墙，空地，每次从起点出发，求到达终点的最少步数；每次移动碰墙停止且墙消失，越出地图或步数大于10则失败；

思路：用bfs不太好写，dfs暴搜；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,s1,s2,num;
int mm[50][50];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x1,int y1,int step)
{
    int i;
    if(step>10)
    {
        return;
    }
    for(i=0;i<4;i++)
    {
        int xx=x1+dir[i][0];
        int yy=y1+dir[i][1];
        if(xx<0||xx>=n||yy<0||yy>=m||mm[xx][yy]==1)
            continue;
        while(xx>=0&&xx<n&&yy>=0&&yy<m&&mm[xx][yy]!=3&&mm[xx][yy]!=1)
        {
            xx+=dir[i][0];yy+=dir[i][1];
        }

        if(mm[xx][yy]==3)
        {
            if(num>step+1)//更新最小步数
            num=step+1;return;
        }
        if(mm[xx][yy]==1)
        {
            mm[xx][yy]=0;
            dfs(xx-dir[i][0],yy-dir[i][1],step+1);
            mm[xx][yy]=1;
        }
    }
}
int main()
{
    int i,j,k;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(n==0&&m==0) break;
        memset(mm,0,sizeof(mm));
        num=12;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                scanf("%d",&mm[i][j]);
                if(mm[i][j]==2)
                {
                    s1=i;s2=j;mm[i][j]=0;
                }
            }
        }
        dfs(s1,s2,0);
        if(num>10) printf("-1\n");
        else printf("%d\n",num);
    }
    return 0;
}