DFS-hdu-2821-Pusher

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2821

题目意思：

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

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

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

解题思路：

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

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

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#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<r;j++)

            printf("%d %s\n",j,save1[j]);

      }*/

      if(!iscan(tmp,i))

         continue;

     /* if(test)

      {

         printf("%d %d->%d %d cnt:%d\n",cur.x,cur.y,tmp.x,tmp.y,cnt);

         putchar('\n');

         for(int j=0;j<r;j++)

            printf("%d %s\n",j,save1[j]);

      }*/

      string tm=ans;

      tm+=di[i];

      if(cnt==lim) //找到了一条路径能全部移完

      {

         an=tm;

         flag=true;

         return ;

      }

      dfs(tmp,tm);

      cnt=temp;  //回溯

      memcpy(save1,tt,sizeof(tt));

   }

}

int main()

{

   while(~scanf("%d%d",&c,&r))

   {

      lim=0;

      for(int i=0;i<r;i++)

      {

         scanf("%s",save[i]);

         for(int j=0;j<c;j++)

            if(save[i][j]!='.')

               lim+=(save[i][j]-'a'+1); //统计箱子个数

      }

      //putchar('\n');

      flag=false;

      for(int i=0;i<r&!flag;i++)

         for(int j=0;j<c&&!flag;j++)

         {

            if(save[i][j]!='.') //枚举开始位置，注意开始位置不为

               continue;

            s.x=i,s.y=j;

            cnt=0;

            memcpy(save1,save,sizeof(save));

            dfs(s,"");

            if(flag)

            {

               printf("%d\n%d\n",i,j);

               cout<<an<<endl;

            }

         }

   }

   return 0;

}

巴特西

DFS-hdu-2821-Pusher

最新文章

热门文章