首页 > 搜索 > DFS搜索 > HDU 2821-Pusher-DFS-[解题报告]HOJ
2014
02-17

HDU 2821-Pusher-DFS-[解题报告]HOJ

Pusher

问题描述 :

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.

输入:

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.)

输出:

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.)

样例输入:

3
7
...
...
.b.
...
...
.a.
...

样例输出:

4
1
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.

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

 按题意DFS就可以了。。。但是我在处理最后结果的时候出现了重大错误,在深搜已经找到结果的时候。。要return!!!!

因为这题搜索时,有4个方向。。如何你找到正确结果不返回,它仍然会继续搜索,在搜索剩下方向时很有可能改变正确的路径答案。。

下面是AC代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
char map[50][50];
int cnt[50][50];
int r,c;
int flag;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int sum;
char op[]="DRUL";
char ans[10000];
int cur_step;
bool cheack(int x,int y){
      if(x>=0&&x<c&&y>=0&&y<r)
      return true;
      return false;
}
void dfs(int x,int y,int cur_sum,int step){
     if(cur_sum==sum){  flag=1;  cur_step=step;return ;}

     for(int i=0;i<4;i++){
         int next_x=x+dir[i][0],next_y=y+dir[i][1];
         if(cnt[next_x][next_y]>0)  continue ;

         while(cnt[next_x][next_y]==0&&cheack(next_x,next_y)){
             next_x+=dir[i][0],next_y+=dir[i][1];
         }
         if(cheack(next_x,next_y)&&cnt[next_x][next_y]>0){
             int x1=next_x+dir[i][0],  y1=next_y+dir[i][1];
             ans[step]=op[i];

             if(cnt[next_x][next_y]==1){
                    cnt[next_x][next_y]=0;
                    dfs(next_x,next_y,cur_sum+1,step+1);
                    if(flag)  return ;                     //要RETURN
                    
                    cnt[next_x][next_y]=1;
             }
             else{
                if(cheack(x1,y1)){
                   cnt[x1][y1]+=cnt[next_x][next_y]-1;
                   int temp=cnt[next_x][next_y];
                   cnt[next_x][next_y]=0;

                   dfs(next_x,next_y,cur_sum+1,step+1);

                    if(flag)  return ;
                   cnt[x1][y1]=cnt[x1][y1]-(temp-1);
                   cnt[next_x][next_y]=temp;
                }
                else{
                   int temp=cnt[next_x][next_y];
                   cnt[next_x][next_y]=0;
                   dfs(next_x,next_y,cur_sum+temp,step+1);

                    if(flag)  return ;
                   cnt[next_x][next_y]=temp;
                }
             }


         }

     }

}
int main(){
    while(cin>>r>>c){

        memset(cnt,0,sizeof(cnt));
        sum=0;

        for(int i=0;i<c;i++)  cin>>map[i];

        for(int i=0;i<c;i++)        for(int j=0;j<r;j++)
        if(map[i][j]=='.')   cnt[i][j]=0;
        else           {     cnt[i][j]=map[i][j]-'a'+1;  sum+=cnt[i][j]; }
        int i,j;  flag=0;  cur_step=0;
        ans[0]='\0';

        for( i=0;i<c;i++){

             for( j=0;j<r;j++)
             if(map[i][j]=='.'){

                dfs(i,j,0,0);
                if(flag) break;
          }
          if(flag)  break;
        }

        ans[cur_step]='\0';
        if(flag){
            printf("%d\n%d\n",i,j);
            printf("%s\n",ans);
        }
    }
    return 0;
}

解题参考:http://blog.csdn.net/w00w12l/article/details/7891149


,
  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.