hdu 2821 Pusher (dfs)

Pusher

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 754 Accepted Submission(s): 264
Special Judge

Problem Description

PusherBoy is an online game http://www.hacker.org/push . There is an R * C grid, and there are piles of blocks on some positions. The goal is to clear the blocks by pushing into them.

You should choose an empty area as the initial position of the PusherBoy. Then you can choose which direction (U for up, D for down, L for left and R for right) to push. Once the direction is chosen, the PusherBoy will walk ahead until he met a pile of blocks (Walking outside the grid is invalid). Then he remove one block from the pile (so if the pile contains only one block, it will become empty), and push the remaining pile of blocks to the next area. (If there have been some blocks in the next area, the two piles will form a new big pile.)

Please note if the pusher is right up against the block, he can't remove and push it. That is, there must be a gap between the pusher and the pile. As the following figure, the pusher can go up, but cannot go down. (The cycle indicates the pusher, and the squares indicate the blocks. The nested squares indicate a pile of two blocks.)

And if a whole pile is pushed outside the grid, it will be considered as cleared.

Input

There are several test cases in each input. The first two lines of each case contain two numbers C and R. (R,C <= 25) Then R lines follow, indicating the grid. '.' stands for an empty area, and a lowercase letter stands for a pile of blocks. ('a' for one block, 'b' for two blocks, 'c' for three, and so on.)

Output

Output three lines for each case. The first two lines contains two numbers x and y, indicating the initial position of the PusherBoy. (0 <= x < R, 0 <= y < C). The third line contains a moving sequence contains 'U', 'D', 'L' and 'R'. Any correct answer will be accepted.

Sample Input

3 7

...

.b.

...

.a.

...

Sample Output

UDU

Hint

Hint: The following figures show the sample. The circle is the position of the pusher. And the squares are blocks (The two nested squares indicating a pile of two blocks). And this is the unique solution for this case.

Source

2009 Multi-University Training Contest 1 - Host by TJU

Recommend

gaojie | We have carefully selected several similar problems for you: 2822 2819 2820 2818 2824

题意：

做了这题后告诉我一个真理，题意真的很重要！！

开始WA以为自己搞错题意了，然后上网看别人解题报告里的题意，让我迷惑的就是在边界的撞过去会怎样，- -本来是觉得应该会飞出去，这样挺好的~~

后来忘了是什么原因错了，一直TLE，就怀疑这个想法(好像没关系...)，看到别人的是不能有这种情况，就按此思路再写再改，后来还是一直WA；于是再看一解题报告，

发现本来的才是对的：http://www.2cto.com/kf/201208/149755.html

题意大概如此，有然若干个可能叠起的方格放在某些格子上，选择任意点作为始点，Pusher可以沿某方向前进把格子推向正对方向的前一格，每次能减少1个，如果前一格有方格就叠起，如果前面一格已出界，就全部推掉了，减少n个。求一个可行解的始点及其操作。

dfs：

弄清楚提议后就好写了，弄了半天，心力交瘁= =我的代码可以优化，不过暂时不想看它了。

暴力n*m个点然后深搜可行解！

  1 //15MS    240K    2251 B    G++    
  2 #include<stdio.h>
  3 #include<string.h>
  4 char c[5]="RDLU";
  5 int mov[4][2]={0,1,1,0,0,-1,-1,0};
  6 char g[30][30];
  7 char root[10000];
  8 int n,m,flag,sum;
  9 int sx,sy;
 10 int judge(int x,int y)
 11 {
 12     if(x>=0&&x<n&&y>=0&&y<m) return 1;
 13     return 0;
 14 }
 15 void dfs(int x,int y,int cnt,int s)
 16 {
 17     if(flag) return;
 18     if(sum==s){
 19         flag=1; root[cnt]=''; return;
 20     }
 21     for(int i=0;i<4;i++){
 22         int tx=x+mov[i][0];
 23         int ty=y+mov[i][1];
 24         if(!judge(tx,ty) || g[tx][ty]) continue;
 25         while(judge(tx,ty) && !g[tx][ty]){
 26             tx+=mov[i][0];ty+=mov[i][1];
 27         }
 28         if(judge(tx,ty) && g[tx][ty]){
 29         int ta=tx+mov[i][0];
 30         int tb=ty+mov[i][1];
 31         root[cnt]=c[i];
 32         int temp=g[tx][ty];
 33         if(g[tx][ty]==1){
 34             g[tx][ty]=0;
 35             dfs(tx,ty,cnt+1,s+1);
 36             if(flag) return;
 37             g[tx][ty]=1;     
 38         }else{
 39             if(judge(ta,tb)){
 40                 g[ta][tb]+=temp-1;
 41                 g[tx][ty]=0;
 42                 dfs(tx,ty,cnt+1,s+1);
 43                 if(flag)return;
 44                 g[ta][tb]-=temp-1;
 45                 g[tx][ty]=temp;
 46             }else{
 47                 g[tx][ty]=0;
 48                 dfs(tx,ty,cnt+1,s+temp);
 49                 if(flag)return;
 50                 g[tx][ty]=temp; 
 51             }
 52         }
 53         }
 54     }
 55     return;
 56 }
 57 int main(void)
 58 {
 59     while(scanf("%d%d",&m,&n)!=EOF)
 60     {
 61         int i,j;
 62         flag=0;
 63         sum=0;
 64         memset(g,0,sizeof(g));
 65         memset(root,0,sizeof(root));
 66         for(i=0;i<n;i++){
 67             scanf("%s",g[i]);
 68             for(j=0;j<m;j++){
 69                 if(g[i][j]=='.') g[i][j]=0;
 70                 else{
 71                     g[i][j]=g[i][j]-'a'+1;
 72                     sum+=g[i][j];
 73                 }
 74             }
 75         }
 76         for(i=0;i<n;i++) if(!flag)
 77             for(int j=0;j<m;j++){
 78                 sx=i;sy=j;
 79                 if(!g[i][j])
 80                     dfs(i,j,0,0);
 81                 if(flag){
 82                     printf("%d
%d
",i,j);
 83                     puts(root);
 84                     break;
 85                 }
 86             }
 87     }
 88     return 0;
 89 }
 90 /*
 91 3
 92 7
 93 ...
 94 ...
 95 .b.
 96 ...
 97 ...
 98 .a.
 99 ...
100 */