tzc 1345 推箱子

推箱子"/>

tzc 1345 推箱子

.do?&method=showdetail&contestId=156&id=1345

游戏的题目 这个题目思想很简单 就是对箱子推DFS 人BFS搜索到达箱子的四个位置  推一次搜索一次 推一次搜索一次

当时忘加一个就是当前箱子是人BFS时候的障碍物  当时没考虑悲剧发生  还好发现了~~~否则郁闷了。。。。。

后来看看 速度不快如果矩阵大点 于是剪枝了

 看看CODE:注释加了比较多的

 #include<stdio.h> #include<string.h> #include<math.h> #include<string.h> #define maxn 21 #define stepmaxn 405 #define inf 0x7fffffff #define min(x,y) (x)>(y)?(y):(x) int map[maxn][maxn],map2[maxn][maxn],m,n,t;int dir[4][2]={0,1,1,0,-1,0,0,-1}; int count;//记录箱子移动最小的步数 char last_step[stepmaxn]; //记录箱子具体怎么走的E S W N 分别表示东南西北 char step[stepmaxn];typedef struct {int x,y; }point; point end; typedef struct {point person;point box; }node;int check(point tt) {return tt.x>=0&&tt.x<m&&tt.y>=0&&tt.y<n&&map[tt.x][tt.y]!=1&&map[tt.x][tt.y]!=5; } int checkb(point tt) {return tt.x>=0&&tt.x<m&&tt.y>=0&&tt.y<n&&map[tt.x][tt.y]!=1; } int checkp(point tt,int mp[][maxn]) {return tt.x>=0&&tt.x<m&&tt.y>=0&&tt.y<n&&mp[tt.x][tt.y]!=1; }//bfs搜索人到箱子四个位置的 int pbfs(point s,point e,point box) {if(s.x==e.x&&s.y==e.y)return 1;point que[maxn*maxn+10000],tt;int head,tail,i,tmp[maxn][maxn];for(i=0;i<maxn;i++)for(int j=0;j<maxn;j++)tmp[i][j]=map2[i][j];tmp[box.x][box.y]=1;//将箱子的位置作为人找四个位置的作为目的地的障碍物 不能穿越箱子而去吧 呵呵head=tail=0;que[tail++]=s;tmp[s.x][s.y]=1;while(head<tail){s = que[head++];for(i=0;i<4;i++){tt.x=s.x+dir[i][0];tt.y=s.y+dir[i][1];if(checkp(tt,tmp)){tmp[tt.x][tt.y]=1;if(tt.x==e.x&&tt.y==e.y){return 1;}que[tail++]=tt;}}}return 0;}//人推箱子的DFS void dfs(node next) {point e,s;node x;int tp=abs(next.box.x-end.x)+abs(next.box.y-end.y);//剪枝if(count!=inf){if((t+tp)>=count)return;//剪枝}if(next.box.x==end.x&&next.box.y==end.y){printf("t = %d/n",t);if(t<count){step[t]='/0';strcpy(last_step,step);count=t;}return ;}//箱子左方向 箱子右移动e.x=next.box.x;e.y=next.box.y-1;s=next.person;if(checkb(e)&&pbfs(s,e,next.box)){point rbox,rperson;rbox.x=next.box.x;rbox.y=next.box.y+1;if(check(rbox)){step[t]='E';//记录点// printf(" right ");//testrperson=next.box;x.box=rbox;x.person=rperson;t++;map[next.box.x][next.box.y]=5;dfs(x);map[next.box.x][next.box.y]=0;t--;}}//箱子右方向 箱子左移动e.x=next.box.x;e.y=next.box.y+1;s=next.person;if(checkb(e)&&pbfs(s,e,next.box)){point rbox,rperson;rbox.x=next.box.x;rbox.y=next.box.y-1;if(check(rbox)){//printf(" left ");//teststep[t]='W';//记录点rperson=next.box;x.box=rbox;x.person=rperson;t++;map[next.box.x][next.box.y]=5;dfs(x);map[next.box.x][next.box.y]=0;t--;}}//箱子上方向 箱子下移动e.x=next.box.x-1;e.y=next.box.y;s=next.person;if(checkb(e)&&pbfs(s,e,next.box)){point rbox,rperson;rbox.x=next.box.x+1;rbox.y=next.box.y;if(check(rbox)){//printf(" down ");//teststep[t]='S';//记录点rperson=next.box;x.box=rbox;x.person=rperson;t++;map[next.box.x][next.box.y]=5;dfs(x);map[next.box.x][next.box.y]=0;t--;}}//箱子下方向 箱子上移动e.x=next.box.x+1;e.y=next.box.y;s=next.person;if(checkb(e)&&pbfs(s,e,next.box)){point rbox,rperson;rbox.x=next.box.x-1;rbox.y=next.box.y;if(check(rbox)){//printf(" up ");//teststep[t]='N';//记录点rperson=next.box;x.box=rbox;x.person=rperson;t++;map[next.box.x][next.box.y]=5;dfs(x);map[next.box.x][next.box.y]=0;t--;}}}int main() {int tt,i,j;node s;scanf("%d",&tt);while(tt--){t=0;count=inf;scanf("%d%d",&m,&n); for(i=0;i<m;i++)for(j=0;j<n;j++){scanf("%d",&map[i][j]);map2[i][j]=map[i][j];if(map[i][j]==3){end.x=i;end.y=j;}if(map[i][j]==2){s.box.x=i;s.box.y=j;}if(map[i][j]==4){s.person.x=i;s.person.y=j;}}//printf("s = %d %d/n",s.box.x,s.box.y);dfs(s);if(count!=inf){printf("%d/n",count);//输出人推箱子最小步数箱子到达终点printf("%s/n",last_step);//输出具体步骤}else{printf("-1/n");//人推箱子到不了}}return 0; }/* 自己写的测试数据还是比较好的 7 6 5 0 0 1 4 0 0 3 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 2 1 0 0 0 0 0 0 6 5 0 0 1 4 0 0 3 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 2 1 0 0 0 0 0 0 5 5 3 1 4 1 0 1 1 0 1 1 1 1 2 1 1 1 1 0 1 1 1 1 0 1 1 6 6 0 1 0 1 0 1 3 0 1 0 1 4 1 0 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 0 1 0 1 0 1 3 0 0 0 1 4 1 0 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 0 1 0 1 0 1 3 0 0 0 1 4 1 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 4 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 3 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 20 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 4 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 3 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 3 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 */