首页 > 搜索 > DFS搜索 > HDU 3500-Fling-DFS-[解题报告]HOJ
2014
04-09

HDU 3500-Fling-DFS-[解题报告]HOJ

Fling

问题描述 :

Fling is a kind of puzzle games available on phone.
This game is played on a board with 7 rows and 8 columns. Each puzzle consists of a set of furballs placed on the board. To solved a puzzle, you need to remove the furballs from board until there is no more than one furball on the board. You do this by ´flinging´ furballs into other furballs, to knock them off the board. You can fling any furballs in four directions (up, left, right, down). The flung furball stops at the front grid of another one as soon as knocking it. And the knocked furball continues to rolling in the same direction until the last knocked one goes off the board. For instance, A furball at (0, 0) rolls right to the furball at (0, 5), then it will stop at (0, 4). Moreover, the latter will roll to right. You cannot fling a furball into a neighbouring furball, the one next to in any of four directions. However, it is permitted for a rolling ball knocks into a ball with a neighbour in that direction.

Flight

输入:

The input contains multiple test cases.
For each case, the 7 lines with 8 characters describe the board. ´X´ represents a empty grid and ´O´ represents a grid with a furball in it. There are no more than 12 furballs in any board.
Each case separated by a blank line.

输出:

The input contains multiple test cases.
For each case, the 7 lines with 8 characters describe the board. ´X´ represents a empty grid and ´O´ represents a grid with a furball in it. There are no more than 12 furballs in any board.
Each case separated by a blank line.

样例输入:

XXXXXXXX
XXOXXXXX
XXXXXXXX
XXXXXXXX
XOXXXXOX
XXXXXXXX
XXXXXXXX

XXXXXXXX
XOXOXOOX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

样例输出:

CASE #1:
4 6 L
1 2 D

CASE #2:
1 1 R
1 4 L
1 3 R

这题题意是一个弹来弹去的游戏。

在一个7*8的板子上,有若干个球(小于12个,经测试最多11个)。

你每次可以选择一个球向上下左右推动,能推动的条件是推动的方向上有球但是不能粘在一起,中间必需得隔一个及以上的格子。

然后你推动这个球后它会一直在这个方向上滚动,直到碰到下一个球或者掉下板子去。

如果碰到下一个球他的动能会传递下去,如果碰到的球紧挨着另一个球就隔山打牛,而原来的球就停在碰到的球的前一个位置上。

然后结束标志是板子上只剩一个球。

输出每次操作的球的坐标和推动的方向(ULRD)。

如果有多种情况就按照越左上角越好和U,L,R,D的优先级输出优先级最高的情况。

起初是想记录下所有的O点保存进结构体,这样就一定满足左上角在前来进行搜索了。

然后把ULRD编作1234进行分类讨论,当搜到满足条件的情况时输出的自然就是优先级最高的解了。

实际上这样也是可行的,但是中途卡了一段时间导致我重新换了思路。

最后我是每次DFS都把地图搜一遍先搜到的先进行操作,结果是一样的。但是可能会慢点。

思路是很简单,但这题烦在回溯和Debug上………………

附代码:

#include <cstdio>
#define MAX 8
using namespace std;
char map[7][MAX];
char s[11][MAX];
int n,flag,total;
struct node{
    int i,j;
    int run;
}road[11];
bool judge(int curi,int curj,int x)              //判断是否可推函数,长了Debug好痛苦。。。
{
    int i;
    if(x==1){
        if(curi-1<0||(map[curi-1][curj]=='O'))
        return 0;
        for(i=2;curi-i>=0;i++)
        if(map[curi-i][curj]=='O')
        return 1;
    }else if(x==2){
        if(curj-1<0||(map[curi][curj-1]=='O'))
        return 0;
        for(i=2;curj-i>=0;i++)
        if(map[curi][curj-i]=='O')
        return 1;
    }else if(x==3){
        if(curj+1>=8||(map[curi][curj+1]=='O'))
        return 0;
        for(i=2;curj+i<8;i++)
        if(map[curi][curj+i]=='O')
        return 1;
    }else if(x==4){
        if(curi+1>=7||(map[curi+1][curj]=='O'))
        return 0;
        for(i=2;curi+i<7;i++)
        if(map[curi+i][curj]=='O')
        return 1;
    }
    return 0;
}
void dfs(){
    int i,j,k,l,l2;
    if(total==n){
        for(i=1;i<total;i++){
            printf("%d %d ",road[i].i,road[i].j);
            if(road[i].run==1)
            printf("U\n");
            else if(road[i].run==2)
            printf("L\n");
            else if(road[i].run==3)
            printf("R\n");
            else if(road[i].run==4)
            printf("D\n");
        }
        flag=1;
        return ;
    }
    for(i=0;i<7;i++){
        for(j=0;j<8;j++){
            if(map[i][j]=='O'){
                for(k=1;k<=4;k++){
                    if(!judge(i,j,k))continue;
                    road[total].i=i;
                    road[total].j=j;
                    road[total].run=k;
                    if(k==1||k==4){
                        for(l=0;l<7;l++){
                            s[total][l]=map[l][j];            //该列改变了,记录该列。
                        }
                    }
                    else{
                        for(l=0;l<8;l++){
                            s[total][l]=map[i][l];           //该行改变了,记录该行。
                        }
                    }
                    map[i][j]='X';
                    if(k==1){                                //分类讨论推动方向
                        l2=i;
                        for(l=i-1;l>=0;l--){
                            if(map[l][j]=='O'){
                                map[l+1][j]='O';
                                if(l2!=l+1){
                                    map[l2][j]='X';
                                }
                                l2=l;
                            }
                        }
                        map[l2][j]='X';
                    }else if(k==2){
                        l2=j;
                        for(l=j-1;l>=0;l--){
                            if(map[i][l]=='O'){
                                map[i][l+1]='O';
                                if(l2!=l+1){
                                    map[i][l2]='X';
                                }
                                l2=l;
                            }
                        }
                        map[i][l2]='X';
                    }else if(k==3){
                        l2=j;
                        for(l=j+1;l<8;l++){
                            if(map[i][l]=='O'){
                                map[i][l-1]='O';
                                if(l-1!=l2){
                                    map[i][l2]='X';
                                }
                                l2=l;
                            }
                        }
                        map[i][l2]='X';
                    }else if(k==4){
                        l2=i;
                        for(l=i+1;l<7;l++){
                            if(map[l][j]=='O'){
                                map[l-1][j]='O';
                                if(l-1!=l2){
                                    map[l2][j]='X';
                                }
                                l2=l;
                            }
                        }
                        map[l2][j]='X';
                    }
                    total++;
                    dfs();
                    if(flag)return ;
                    total--;
                    if(k==1||k==4){                         //进行回溯。
                        for(l=0;l<7;l++){
                                map[l][j]=s[total][l];
                            }
                    }
                    else{
                        for(l=0;l<8;l++){
                            map[i][l]=s[total][l];
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    int casi=0;
    int i,j;
    while(scanf("%s",s[0])!=EOF){
            if(casi)printf("\n");
            n=0;
            for(i=0;i<8;i++){
                map[0][i]=s[0][i];
                if(map[0][i]=='O')
                n++;
            }
            for(i=1;i<7;i++){
                scanf("%s",s[0]);
                for(j=0;j<8;j++){
                    map[i][j]=s[0][j];
                    if(map[i][j]=='O')
                    n++;
                }
            }
            flag=0;
            total=1;
            printf("CASE #%d:\n",++casi);
            dfs();
    }
    return 0;
}

234MS过的,速度不错。但是因为代码长因此Debug了很久,这题思路就是简单的搜每个点看其能不能推,能推就搜,失败了就回溯。

时限是3000MS,其实可以整体保存来回溯(虽然会慢点),然后将方向也数字化,这样代码量会大量缩短错误率也会降低。

参考:http://blog.csdn.net/beenlast/article/details/6595553


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

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮