DFS-hdu-2821-Pusher-白红宇

DFS-hdu-2821-Pusher

阅读量：5301 次

发布时间：2019-06-14

本文共 2141 字，大约阅读时间需要 7 分钟。

题目链接：

题目意思：

给一个n*n的矩阵，里面有些位置是空的，有些位置有箱子（a代表一个箱子，b代表两个，依此类推）。让你选择一个空位置作为起点，然后每步选择一个方向（上，下，左，右）走，直到碰到箱子为止，然后将此位置的箱子移走一个，剩下的箱子全部合并到下一位置。要求：必须与箱子隔超过1个位置的时候才能移。

求一个开始位置使得能够移除所有的箱子，并输出行走路线。

经数据检测两点注意：1、不含边缘位置超过一个箱子的情况，2、保证有解。

解题思路：

枚举开始位置，DFS深搜，有一条路径能全部移走箱子，则输出。

注意保存回溯现场（不要用全局变量来保存现场，因为在递归调用的时候会覆盖原来保存的现场，wa了好几次）。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define eps 1e-6#define INF 0x1f1f1f1f#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;/*freopen("data.in","r",stdin);freopen("data.out","w",stdout);*/char save[30][30],save1[30][30];int c,r,dir[4][2]={ {-1,0},{0,1},{1,0},{0,-1}};int lim,cnt;char di[4]={'U','R','D','L'};struct Inf{ int x,y;}s;bool iscan(Inf & tt,int dd){ int xx=tt.x+dir[dd][0],yy=tt.y+dir[dd][1]; if(xx<0||xx>=r||yy<0||yy>=c) //下一步出界了，不行 return false; if(save1[xx][yy]!='.') //下一步就是箱子不行 return false; while(save1[xx][yy]=='.') //在该方向走，直到靠近箱子为止 { xx=xx+dir[dd][0],yy=yy+dir[dd][1]; if(xx<0||xx>=r||yy<0||yy>=c)//走出去了，不行 return false; } if(save1[xx][yy]=='a')//该位置只有一个箱子 { cnt++; save1[xx][yy]='.'; tt.x=xx,tt.y=yy; return true; } else //该位置有多个箱子 { int x=xx+dir[dd][0],y=yy+dir[dd][1]; if(x<0||x>=r||y<0||y>=c) //边缘有多个箱子的情况 { //cnt++; //tt.x=xx,tt.y=yy; //save1[xx][yy]=save1[xx][yy]-1; //return true; //两种写法都可以，其他写法也行，因为测试数据中不存在这种情况 return false; } cnt++; tt.x=xx,tt.y=yy; if(save1[x][y]!='.') //下一位置如果不是.的话，直接合并 save1[x][y]=save1[x][y]+save1[xx][yy]-'a';//注意-'a' else //下一位置是.的话，直接拿过来 save1[x][y]=save1[xx][yy]-1; save1[xx][yy]='.'; return true; }}bool flag;string an;void dfs(Inf cur,string ans){ if(flag) //已找到一条路径 return ; char tt[30][30];//注意保存现场时要用局部变量 for(int i=0;i<4;i++) //沿四个方向走 { memcpy(tt,save1,sizeof(save1)); Inf tmp=cur; int temp=cnt; //便于回溯的时候，其他没有改变 /*if(test) { for(int j=0;j
                 
                  %d %d cnt:%d\n",cur.x,cur.y,tmp.x,tmp.y,cnt); putchar('\n'); for(int j=0;j

转载于:https://www.cnblogs.com/jiangu66/p/3238886.html

你可能感兴趣的文章

English trip -- VC(情景课)1 C What's your name?（review）