POJ3009 Curling

时间:2023-03-09 06:59:21
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[][];
int ans, n, m;
const int dir[][] = {, -, , , , , -, };
int limit(int x, int y)
{
return (x>&&x<=n&&y>&&y<=m);
} void dfs(int x, int y, int step)
{
if(step>=) return;
for(int i=; i<; i++)
{
int nx = x+dir[i][];
int ny = y+dir[i][];
if(limit(nx, ny)&&pic[nx][ny]!=)
{
while(limit(nx, ny)&&pic[nx][ny]!=&&pic[nx][ny]!=)
{
nx +=dir[i][];
ny += dir[i][];
}
if(pic[nx][ny]==)
{
if(ans>step+)
ans = step+;
return;
}
else if(pic[nx][ny]==)
{
pic[nx][ny] = ;
dfs(nx-dir[i][], ny-dir[i][], step+);
pic[nx][ny] = ;
}
}
}
} int main()
{
int x, y;
while(scanf("%d%d", &m, &n), n||m)
{
memset(pic, , sizeof(pic));
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
{
scanf("%d", &pic[i][j]);
if(pic[i][j]==)
{
x = i;
y = j;
}
}
ans = 0x7fff;
dfs(x, y, );
if(ans>)
printf("-1\n");
else
printf("%d\n", ans);
}
return ;
}