推箱子
题目：http://acm.hdu.调了2天了，都没调出什么问题，各位帮我看看吧
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int visit[20][20][20];
int mark[20][20];
int judgeman(int x,int y,int n,int m,int map[20][20])
{
if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!=1&&mark[x][y]==0)
{
mark[x][y]=1;
return 1;
}
return 0;
}
int judge(int x,int y,int n,int m,int map[20][20])
{
if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!=1&&map[x][y]!=2)
return 1;
return 0;
}
int dfsman(int map[20][20],int n,int m,int startx,int starty,int endx,int endy)//判断是否能到达箱子的一端
{
int queue[200][3];
int head=0,tail=1,ans=0,x,y,xx,yy,i;
memset(queue,0,sizeof(queue));
memset(mark,0,sizeof(mark));
queue[0][0]=startx;queue[0][1]=starty;
queue[0][2]=0;
while(head<tail)
{
x=queue[head][0];
y=queue[head][1];
ans=queue[head][2];
//printf("%d %d %d\n",x+1,y+1,ans);
if(x==endx&&y==endy) return 1;
head++;
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(judgeman(xx,yy,n,m,map)==1)
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=ans+1;
tail++;
}
}
}
return 0;
}
void dfs(int map[20][20],int n,int m,int startx,int starty,int endx,int endy,int boxx,int boxy)
{
int queue[400][5];
int head=0,tail=1,x,y,mx,my,xx,yy,step,i;
memset(queue,0,sizeof(queue));
queue[0][0]=boxx;//箱子位置
queue[0][1]=boxy;
queue[0][2]=startx;//人的位置
queue[0][3]=starty;
queue[0][4]=0;//步数
while(head<tail)
{
if(dfsman(map,n,m,startx,starty,boxx,boxy)==0) break;//判断小人是否能到达箱子，如果不能说明小人被围墙困住
x=queue[head][0];//箱子位置
y=queue[head][1];
mx=queue[head][2];//人的位置
my=queue[head][3];
step=queue[head][4];//步数
head++;
if(x==endx&&y==endy)//假如箱子达到目的地打印step
{
printf("%d\n",step);
return ;
}
for(i=0;i<4;i++)
{
xx=x+dx[i]; yy=y+dy[i];
mx=x+dx[i]; my=y+dy[i];
if(judge(xx,yy,n,m,map)==0||judge(mx,my,n,m,map)==0)
continue;
if(visit[xx][yy][i]==0&&dfsman(map,n,m,mx,my,xx,yy)==1)//visit[xx][yy][i] i为从那个方向推来的
{
visit[xx][yy][i]=1;
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=mx;
queue[tail][3]=my;
queue[tail][4]=step+1;
tail++;
}
}
}
printf("-1\n");
}
int main()
{
int map[20][20],n,m,t,startx,starty,endx,endy,boxx,boxy;
int i,j;
memset(visit,0,sizeof(visit));
memset(map,0,sizeof(map));
scanf("%d",&t);
while(t>=1)
{
scanf("%d %d",&m,&n);//m行n列的迷宫
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==4)
startx=i,starty=j;//人的位置
if(map[i][j]==3)
endx=i,endy=j;//箱子的目的地
if(map[i][j]==2)
boxx=i,boxy=j;//箱子的所在位置
}
dfs(map,n,m,startx,starty,endx,endy,boxx,boxy);
t--;
}
system("pause");
return 0;
}
/*
1
7 4
1 4 1 1
1 2 1 1
1 0 1 1
1 0 1 1
1 0 1 1
1 0 1 1
1 3 1 1
*/
[ 本帖最后由 sunyh1999 于 2011-5-1 15:48 编辑 ]
