POJ3009 Curling

题目链接：http://poj.org/problem?id=3009

题意：从2出发，要到达3， 0可以通过，碰到1要停止，并且1处要变成0， 并且从起点开始沿着一个方向要一直前进，直至碰到1（或者3）处才能停止，（就是反射来反射去知道反射经过3）.如果反射10次还不能到达3，就输出-1.

#include<cstdio>
#include<cstring>
int pic[25][25];
int ans, n, m;
const int dir[4][2] = {0, -1, 0, 1, 1, 0, -1, 0};
int limit(int x, int y)
{
    return (x>0&&x<=n&&y>0&&y<=m);
}

void dfs(int x, int y, int step)
{
    if(step>=10) return;
    for(int i=0; i<4; i++)
    {
        int nx = x+dir[i][0];
        int ny = y+dir[i][1];
        if(limit(nx, ny)&&pic[nx][ny]!=1)
        {
            while(limit(nx, ny)&&pic[nx][ny]!=1&&pic[nx][ny]!=3)
            {
                nx +=dir[i][0];
                ny += dir[i][1];
            }
            if(pic[nx][ny]==3)
            {
                if(ans>step+1)
                ans = step+1;
                return;
            }
            else if(pic[nx][ny]==1)
            {
                pic[nx][ny] = 0;
                dfs(nx-dir[i][0], ny-dir[i][1], step+1);
                pic[nx][ny] = 1;
            }
        }
    }
}

int main()
{
    int x, y;
    while(scanf("%d%d", &m, &n), n||m)
    {
        memset(pic, 0, sizeof(pic));
        for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            scanf("%d", &pic[i][j]);
            if(pic[i][j]==2)
            {
                x = i;
                y = j;
            }
        }
        ans = 0x7fff;
        dfs(x, y, 0);
        if(ans>10)
        printf("-1
");
        else 
        printf("%d
", ans);
    }
    return 0;
}