POJ_3009
一开始没有考虑周全，导致做这个题目的时候很是坎坷。
首先，石头在移动的过程中，是可能在同一位置出现两次的，因而用vis[][]进行判重是不可取的，同时也正是基于这一点，用dis[][]去记录最短距离也同样是不可取的。
其次，由于这个题目一次碰撞会让Block消失，因而会影响下面的操作，所以一般的BFS是行不通的。
考虑到上面两点之后，便放弃BFS，而改用DFS。
这个题目如果不限定解的深度而直接DFS会超时，所以在DFS过程中要限定解的深度在10及10以内。如果这个题目解的深度更深的话，还可以考虑用叠代加深的方式去DFS。
#include<stdio.h>
#include<string.h>
int a[21][21],count,min;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int sx,sy,tx,ty,w,h;
void dfs(x,y)
{
int i,newx,newy;
if(count>9)
return;
for(i=0;i<2;i++)
{
newx=x+dx[i];
if(newx<0||newx>h-1||a[newx][y]==1)
continue;
while(newx+dx[i]>=0&&newx+dx[i]<=h-1)
{
if(a[newx][y]==3)
{
if(count+1<min)
min=count+1;
return;
}
if(a[newx+dx[i]][y]==1)
break;
newx+=dx[i];
}
if(a[newx][y]==3)
{
if(count+1<min)
min=count+1;
return;
}
if(newx<=0||newx>=h-1)
continue;
a[newx+dx[i]][y]=0;
count++;
dfs(newx,y);
a[newx+dx[i]][y]=1;
count--;
}
for(;i<4;i++)
{
newy=y+dy[i];
if(newy<0||newy>w-1||a[x][newy]==1)
continue;
while(newy+dy[i]>=0&&newy+dy[i]<=w-1)
{
if(a[x][newy]==3)
{
if(count+1<min)
min=count+1;
return;
}
if(a[x][newy+dy[i]]==1)
break;
newy+=dy[i];
}
if(a[x][newy]==3)
{
if(count+1<min)
min=count+1;
return;
}
if(newy<=0||newy>=w-1)
continue;
a[x][newy+dy[i]]=0;
count++;
dfs(x,newy);
a[x][newy+dy[i]]=1;
count--;
}
}
int main()
{
int i,j,k;
while(1)
{
scanf("%d%d",&w,&h);
if(w==0)
break;
for(i=0;i<h;i++)
for(j=0;j<w;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==2)
{
sx=i;
sy=j;
}
else if(a[i][j]==3)
{
tx=i;
ty=j;
}
}
count=0;
min=1000000000;
dfs(sx,sy);
if(min>0&&min<=10)
printf("%d\n",min);
else
printf("-1\n");
}
return 0;
}