POJ 3009 Curling 2.0 回溯,dfs 难度:0

http://poj.org/problem?id=3009

如果目前起点紧挨着终点,可以直接向终点滚(终点不算障碍)

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = ;

int maz[maxn][maxn];

int n,m;

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

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

bool in(int x,int y)

{

    return x >=  && x < n  && y >=  && y < m;

}

bool dfs(int x,int y,int step)

{

    if(step == )return maz[x][y] == ;

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

    {

        int tx = x + dx[i],ty = y + dy[i];

        if(maz[tx][ty] == )continue;

        while(in(tx,ty) && maz[tx][ty] == )

        {

            tx += dx[i];

            ty += dy[i];

        }

        if(!in(tx,ty))continue;

        if(maz[tx][ty] == )return true;

        maz[tx][ty] = ;

        if(dfs(tx - dx[i],ty - dy[i],step - ))

        {

            return true;

        }

        maz[tx][ty] = ;

    }

    return false;

}

int main()

{

    while(scanf("%d%d",&m,&n) ==  && (m || n))

    {

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

        {

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

            {

                scanf("%d",maz[i] + j);

            }

        }

        for(int x = ; x < n; x++)

        {

            for(int y = ; y < m; y++)

            {

                if(maz[x][y] == )

                {

                    maz[x][y] = ;

                    bool fl = false;

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

                    {

                        if(dfs(x, y ,i))

                        {

                            fl = true;

                            printf("%d\n",i);

                            break;

                        }

                    }

                    if(!fl)

                    {

                        puts("-1");

                    }

                    break;

                }

            }

        }

    }

    return ;

}