首页 > 搜索 > DFS搜索 > hdu 2414 Chessboard Dance-DFS-[解题报告]C++
2014
01-26

hdu 2414 Chessboard Dance-DFS-[解题报告]C++

Chessboard Dance

问题描述 :

Another boring Friday afternoon, Betty the Beetle thinks how to amuse herself. She goes out of her hiding place to take a walk around the living room in Bennett’s house. Mr. and Mrs. Bennett are out to the theatre and there is a chessboard on the table! "The best time to practice my chessboard dance," Betty thinks! She gets so excited that she does not note that there are some pieces left on the board and starts the practice session! She has a script showing her how to move on the chessboard. The script is a sequence like the following example:

At each instant of time Betty, stands on a square of the chessboard, facing one of the four directions (up, down, left, right) when the board is viewed from the above. Performing a "move n" instruction, she moves n squares forward in her current direction. If moving n squares goes outside the board, she stays at the last square on the board and does not go out. There are three types of turns: turn right, turn left, and turn back, which change the direction of Betty. Note that turning does not change the position of Betty.

If Betty faces a chess piece when moving, she pushes that piece, together with all other pieces behind (a tough beetle she is!). This may cause some pieces fall of the edge of the chessboard, but she doesn’t care! For example, in the following figure, the left board shows the initial state and the right board shows the state after performing the script in the above example. Upper-case and lower-case letters indicate the white and black pieces respectively. The arrow shows the position of Betty along with her direction. Note that during the first move, the black king (r) falls off the right edge of the board!


You are to write a program that reads the initial state of the board as well as the practice dance script, and writes the final state of the board after the practice.

输入:

There are multiple test cases in the input. Each test case has two parts: the initial state of the board and the script. The board comes in eight lines of eight characters. The letters r, d, t, a, c, p indicate black pieces, R, D, T, A, C, P indicate the white pieces and the period (dot) character indicates an empty square. The square from which Betty starts dancing is specified by one of the four characters <, >, ^, and v which also indicates her initial direction (left, right, up, and down respectively). Note that the input is not necessarily a valid chess game status.

The script comes immediately after the board. It consists of several lines (between 0 and 1000). In each line, there is one instruction in one of the following formats (n is a non-negative integer number):

move n
turn left
turn right
turn back

At the end of each test case, there is a line containing a single # character. The last line of the input contains two dash characters.

输出:

There are multiple test cases in the input. Each test case has two parts: the initial state of the board and the script. The board comes in eight lines of eight characters. The letters r, d, t, a, c, p indicate black pieces, R, D, T, A, C, P indicate the white pieces and the period (dot) character indicates an empty square. The square from which Betty starts dancing is specified by one of the four characters <, >, ^, and v which also indicates her initial direction (left, right, up, and down respectively). Note that the input is not necessarily a valid chess game status.

The script comes immediately after the board. It consists of several lines (between 0 and 1000). In each line, there is one instruction in one of the following formats (n is a non-negative integer number):

move n
turn left
turn right
turn back

At the end of each test case, there is a line containing a single # character. The last line of the input contains two dash characters.

样例输入:

.....c..
.p..A..t
D..>T.Pr
....aP.P
p.d.C...
.....p.R
........
........
move 2
turn right
move 3
turn left
turn left
move 1
#
--

样例输出:

.....c..
.p..A..t
D.....TP
....a..P
p.d.C^..
.......R
.....P..
.....p..

题意:推箱子,可以把箱子推出棋盘外,可以推动连续的箱子,当到达边界时,不能往外走哦。

一步一步走。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
char m[20][20];
struct point
{
    int x,y;
    int dir;
} p;
char dir[]= {'v','>','^','<'};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
    if(m[x][y]=='.')
    {
        m[x][y]=m[x-dx[p.dir]][y-dy[p.dir]];
        m[x-dx[p.dir]][y-dy[p.dir]]='.';
    }
    else
    {
        dfs(x+dx[p.dir],y+dy[p.dir]);
        m[x][y]=m[x-dx[p.dir]][y-dy[p.dir]];
        m[x-dx[p.dir]][y-dy[p.dir]]='.';
    }
}
bool oor(int x,int y)
{
    if(x<1||x>8) return false;
    if(y<1||y>8) return false;
    return true;
}
void deal()
{
    for(int i=0;i<9;i++)
    m[0][i]=m[i][0]=m[9][i]=m[i][9]='.';
    m[p.x][p.y]='.';
    if(!oor(p.x+dx[p.dir],p.y+dy[p.dir])) return ;
    dfs(p.x+dx[p.dir],p.y+dy[p.dir]);
    p.x=p.x+dx[p.dir];p.y=p.y+dy[p.dir];
}
void out()
{
    m[p.x][p.y] = dir[p.dir];
    for(int i=1;i<9;i++)
    {
        for(int j=1;j<9;j++) printf("%c",m[i][j]);
        printf("\n");
    }
    printf("\n");
}
int main()
{
    freopen("in.txt","r",stdin);
    while(~scanf("%s",m[1]+1)&&m[1][1]!='-')
    {
        for(int i=2; i<9; i++)
            scanf("%s",m[i]+1);
        for(int i =1; i<9; i++)
        {
            for(int j=1; j<9; j++)
                if(m[i][j]=='v')
                    p.x=i,p.y=j,p.dir=0;
                else if(m[i][j]=='>')
                    p.x=i,p.y=j,p.dir=1;
                else if(m[i][j]=='^')
                    p.x=i,p.y=j,p.dir=2;
                else if(m[i][j]=='<')
                    p.x=i,p.y=j,p.dir=3;
        }
        char op1[10],op2[10];int op3;
        while(scanf("%s",op1)&&op1[0]!='#')
        {
            if(op1[0]=='t')
            {
                scanf("%s",op2);
                if(op2[0]=='l')
                p.dir=(p.dir+1)%4;
                else if(op2[0]=='r')
                p.dir=(p.dir+3)%4;
                else
                p.dir=(p.dir+2)%4;
            }
            else
            {
                scanf("%d",&op3);
                for(int i=0;i<op3;i++)
                deal();
            }
        }
        out();
    }
    return 0;
}

解题转自:http://blog.csdn.net/binwin20/article/details/7835832


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }