POJ3009 Curling 2.0(DFS)

POJ3009 Curling 2.0(DFS)

迷宮問題求最短路。略有不同的是如果不碰到石頭的話會沿著一個方向一直前進，出界就算輸了。碰到石頭，前方石頭會消失，冰壺停在原地。把這個當作狀態的轉移。DFS可以求出其最小操作數。

#include
#include
#include
#include
#include
#include
#include
#include
#define ll __int64
#define INF 0x3f3f3f
using namespace std;

int n,m;
int ex,ey;
int Min;
int dir[4][2]= {{1,0},{0,1},{0,-1},{-1,0}};
int map[25][25];

void dfs(int x,int y,int count)
{
    if(count>10) return;
    for(int i=0; i<4; i++)
    {
        int move_ok=0;
        int xx=x,yy=y;
        if(map[x+dir[i][0]][y+dir[i][1]]==1) continue;
        while(true)
        {
            xx=xx+dir[i][0];
            yy=yy+dir[i][1];
            if(xx<0||xx>=n||yy<0||yy>=m) break;
            if(map[xx][yy]==1)
            {
                move_ok=1;
                break;
            }
            if(map[xx][yy]==3)
            {
                if(Min>count)
                {
                    Min=count;
                    break;
                }
            }
        }
        if(move_ok)
        {
            map[xx][yy]=0;
            dfs(xx-dir[i][0],yy-dir[i][1],count+1);
            map[xx][yy]=1;
        }
    }
}

int main()
{
    //freopen("d:\\test.txt","r",stdin);
    int sx,sy;
    while(cin>>m>>n)
    {
        if(m==0&&n==0) break;
        memset(map,0,sizeof(map));
        for(int i=0; i>map[i][j];
                if(map[i][j]==2)
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        Min=11;
        dfs(sx,sy,1);
        if(Min>10) cout<<"-1"<