首页 > ACM题库 > HDU-杭电 > hdu 1182 Chessmen[解题报告]
2013
12-03

hdu 1182 Chessmen[解题报告]

Chessmen

问题描述 :

You know, Harry, Ron, and Hermione thought they had found some Snape’s cabal. They tried to tail after Snape until they went into a strange room.
The room was so dark they couldn’t see anything at all. But as they stepped into it, light suddenly flooded the room to reveal an astonishing sight.
They were standingon the edge of a huge chessboard, behind the black chessmen, which were all taller than they were and carved from what looked like black stone. Facing them, way across the room, were the white pieces. Harry, Ron and Hermione shivered slightly – the towering white chessmen had no faces.
‘Now what do we do?’ harry whispered.
‘It’s obvious, isn’t it?’ said Ron. ‘We’ve got to play our way across the room.’
Behind the white pieces they could see another door.
‘How?’ said Hermione nervously.
‘I think,’ said Ron, ‘we’re going to have to be chessmen.’
He walked up to a black knight and put his hand out to touch the knight’s horse. At once, the stone sprang to life. The horse pawed the ground and the knight turned his helmeted head to look down at Ron.
‘Do we – er – have to join you to get across?’
The black knight nodded. Ron turned to the other two.
‘This wants thinking about …’ he said. ‘I suppose we’ve got to take the place of the back pieces …’
Harry and Hermione stayed quiet, watching Ron think. Finally he said, ‘Now, don’t be offended or anything, but neither of you are that good at chess -’
‘We’re not offended,’ said Harry quickly. ‘Just tell us what to do.’
‘Well, Harry, you take the place of that bishop, and Hermione, you go next to him instead of that castle.’
‘What about you?’
‘I’m going to be a knight,’ said Ron.
The chessmen seemed to have been listening, because at these words a knight, a bishop and a castle turned there backs on the white pieces and walked off the board leaving three empty squares which Harry, Ron and Hermione took.
‘White always plays first in chess,’ said Ron,peering across the board. ‘Yes … look …’
A white pawn had moved forward two squares.Now Ron decided to direct the black pieces, but he met a trouble. All the chessmen were so tall that he can’t know the whole board. He must memorize the board all by himself if you don’t help him. Could you write a magic for him?

输入:

The input will contain several chess manuals. Each one is in the format as sample input.
O-O and O-O-O will not appear.
Notice that black side may haven’t a move in the last turn.
The input will always be correct,and end of -1.

输出:

Print the chessboard in FEN.
(see also the Hint)

样例输入:

0 Pe2-e4 pd7-d5
1 Pd2-d3 pf7-f5
2 Pf2-f3 pe7-e6
3 Pe4xd5 pe6xd5
4 Pc2-c4 pd5xc4
5 Pd3xc4 qd8-e7
6 Ng1-e2

样例输出:

rnb1kbnr/ppp1q1pp/8/5p2/2P5/5P2/PP2N1PP/RNBQKB1R
Hint

Hint

 
In the FEN (Forsyth-Edwards Notation), a chessboard is described as follows: 
The Board-Content is specified starting with the top row and ending with the bottom row. 
Character / is used to separate data of adjacent rows. 
Each row is specified from left to right. 
White pieces are identified by uppercase piece letters: PNBRQK. 
Black pieces are identified by lowercase piece letters: pnbrqk. 
Empty squares are represented by the numbers one through eight. 
A number used represents the count of contiguous empty squares along a row. 
Each row's sum of numbers and characters must equal 8. 
For example: 
5k1r/2q3p1/p3p2p/1B3p1Q/n4P2/6P1/bbP2N1P/1K1RR3
is the FEN notation description of the following chessboard:

The chessboard of the beginning of a chess game is described in FEN as: 
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

HDU 1182 Strange Billboard

#include<iostream>
#include<memory>
using namespace std;
#define MAXN 18
#define maxint 0x7fffffff

int t[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
char g[MAXN][MAXN];
int row,col;
int sg[MAXN];
int e[65536],tbit[65536];

int dynamic()
{
    int i,j,k,ps,ts,pp,tp,ans,cnt;
    memset( sg , 0 , sizeof(sg) );
    for( i=0 ; i<row ; i++ )
        for( j=0 ; j<col ; j++ )
            if( g[i][j]==’X’ )
                sg[i] += t[j];
    ans = maxint;
    for( i=0 ; i<t[col] ; i++ )
    {
        ts = (sg[0]^e[i])%t[col];
        cnt = tbit[i];
        ps = ts , pp = i;
        for( j=1 ; j<row ; j++ )
        {
            ts = (e[ps]^sg[j]^pp)%t[col];
            cnt += tbit[ps];
            pp = ps , ps = ts;
        }
        if( ts%t[col]==0&&cnt<ans ) ans = cnt;
    }
    if( ans==maxint )
        return -1;
    return ans;
}
int main()
{
    int i,j,t1,t2,tt;
    memset( tbit , 0 , sizeof(tbit) );
    for( i=0 ; i<65536 ; i++ )
    {
        for( t1=0,t2=i,j=0 ; t2 ; j++,t2>>=1 )
        {
            if( !(t2&0×01) ) continue;
            tbit[i] = tbit[i]+1;
            t1 ^= t[j];
            if( j>0 ) t1 ^= t[j-1];
            if( j+1<16 ) t1 ^= t[j+1];
        }
        e[i] = t1;
    }
    while(scanf("%d%d",&row,&col)!=-1)
    {
        if( row==0&&col==0 ) break;
        for( i=0 ; i<row ; i++ )
            scanf( "%s" , g[i] );
        tt = dynamic();
        if( tt>=0 )
            printf("You have to tap %d tiles.\n",tt);
        else
            printf("Damaged billboard.\n");
    }
}

解题转自:http://hi.baidu.com/_green_hand_/item/344eeb18ea54d99a99ce339d