思路&题解

PC/UVA 110107/10196
本题略恶心。模拟

//author: CHC
//First Edit Time:	2014-01-13 17:11
//Last Edit Time:	2014-01-14 13:57
//Filename:1.cpp
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
char map[10][10];
struct jue
{
    int x,y;
    char ch;
}white[100],black[100];
int wn,bn;
int getmap()
{
    int flag=0;
    bn=wn=0;
    memset(map,'0',sizeof(map));
    for(int i=1;i<=8;i++)
    for(int j=1;j<=8;j++)
    {
        scanf(" %c",&map[i][j]);
        if(map[i][j]>='a'&&map[i][j]<='z')//小写是黑方
        {
            black[bn].x=i;
            black[bn].y=j;
            black[bn].ch=map[i][j];
            ++bn;
            flag=1;
        }
        else if(map[i][j]>='A'&&map[i][j]<='Z')//大写是白方
        {
            white[wn].x=i;
            white[wn].y=j;
            white[wn].ch=map[i][j];
            ++wn;
            flag=1;
        }
    }
    return flag;
}
int dx[]={  1,1,-1,-1, 2,2,-2,-2 };
int dy[]={ -2,2, 2,-2,-1,1,-1, 1 };
int checkxiang(int x,int y,char target)
{
    int tx=x,ty=y;
    while(tx>0&&ty>0)
    {
        tx--;ty--;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(tx>0&&ty<=8)
    {
        tx--;ty++;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(tx<=8&&ty>0)
    {
        tx++;ty--;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(tx<=8&&ty<=8)
    {
        tx++;ty++;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    return 0;
}
int checkju(int x,int y,char target)
{
    int tx=x,ty=y;
    while(tx>0)
    {
        tx--;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(tx<=8)
    {
        tx++;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(ty>0)
    {
        ty--;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    tx=x,ty=y;
    while(ty<=8)
    {
        ty++;
        if(map[tx][ty]==target)return 1;
        else if(map[tx][ty]!='.')break;
    }
    return 0;
}
int checkhou(int x,int y,char target)
{
    return checkxiang(x,y,target)||checkju(x,y,target);
}
int checkma(int x,int y,char target)
{
    for(int i=0;i<8;i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx<1||tx>8||ty<1||ty>8)continue;
        if(map[tx][ty]==target)return 1;
    }
    return 0;
}
int checkwhite()//白方在棋盘下部
{//大写是白方
    for(int i=0;i<wn;i++)
    {
        char ch=white[i].ch;
        int x=white[i].x,y=white[i].y;
        //printf("%d %d %c\n",x,y,ch);
        if(ch=='P'){//小兵
            if(map[x-1][y-1]=='k'||map[x-1][y+1]=='k')return 1;
        }
        else if(ch=='N'){//马
            if(checkma(x,y,'k'))return 1;
        }
        else if(ch=='B'){//象
            if(checkxiang(x,y,'k'))return 1;
        }
        else if(ch=='R'){//车
            if(checkju(x,y,'k'))return 1;
        }
        else if(ch=='Q'){//后
            if(checkhou(x,y,'k'))return 1;
        }
    }
    return 0;
}
int checkblack()//黑方在上部
{//小写是黑方
    for(int i=0;i<bn;i++)
    {
        char ch=black[i].ch;
        int x=black[i].x,y=black[i].y;
        //printf("%d %d %c\n",x,y,ch);
        if(ch=='p'){//小兵
            if(map[x+1][y+1]=='K'||map[x+1][y-1]=='K')return 1;
        }
        else if(ch=='n'){//马
            if(checkma(x,y,'K'))return 1;
        }
        else if(ch=='b'){//象
            if(checkxiang(x,y,'K'))return 1;
        }
        else if(ch=='r'){//车
            if(checkju(x,y,'K'))return 1;
        }
        else if(ch=='q'){//后
            if(checkhou(x,y,'K'))return 1;
        }
    }
    return 0;
}
int main()
{
    int cas=0;
    while(getmap())
    {
        int w=checkwhite();
        int b=checkblack();
        if(w)printf("Game #%d: black king is in check.\n",++cas);
        else if(b)printf("Game #%d: white king is in check.\n",++cas);
        else printf("Game #%d: no king is in check.\n",++cas);
    }
    return 0;
}

Check the Check

Your task is to write a program that reads a chessboard configuration and identifies whether a king is under attack (in check). A king is in check if it is on square which can be taken by the opponent on his next move.
White pieces will be represented by uppercase letters, and black pieces by lowercase letters. The white side will always be on the bottom of the board, with the black side always on the top.
For those unfamiliar with chess, here are the movements of each piece:
Pawn (p or P):can only move straight ahead, one square at a time. However, it takes pieces diagonally, and that is what concerns you in this problem.
Knight (n or N): has an L-shaped movement shown below. It is the only piece that can jump over other pieces.
Bishop (b or B): can move any number of squares diagonally, either forward or backward.
Rook (r or R): can move any number of squares vertically or horizontally, either forward or backward.
Queen (q or Q): can move any number of squares in any direction (diagonally, horizontally, or vertically) either forward or backward.
King (k or K): can move one square at a time in any direction (diagonally, horizontally, or vertically) either forward or backward.
Movement examples are shown below, where ‘*’ indicates the positions where the piece can capture another piece:

 Pawn          Rook          Bishop        Queen         King          Knight  
 ........      ...*....      .......*      ...*...*      ........      ........  
 ........      ...*....      *.....*.      *..*..*.      ........      ........  
 ........      ...*....      .*...*..      .*.*.*..      ........      ..*.*...  
 ........      ...*....      ..*.*...      ..***...      ..***...      .*...*..  
 ...p....      ***r****      ...b....      ***q****      ..*k*...      ...n....  
 ..*.*...      ...*....      ..*.*...      ..***...      ..***...      .*...*..  
 ........      ...*....      .*...*..      .*.*.*..      ........      ..*.*...  
 ........      ...*....      *.....*.      *..*..*.      ........      ........

Remember that the knight is the only piece that can jump over other pieces. The pawn movement will depend on its side. If it is a black pawn, it can only move one square diagonally down the board. If it is a white pawn, it can only move one square diagonally up the board. The example above is a black pawn, described by a lowercase ‘p’. We use move to indicate the squares where the pawn can capture another piece.

Input

There will be an arbitrary number of board configurations in the input, each consisting of eight lines of eight characters each. A ‘.’ denotes an empty square, while upper- and lowercase letters represent the pieces as defined above. There will be no invalid characters and no configurations where both kings are in check. You must read until you find an empty board consisting only of ‘.’ characters, which should not be processed. There will be an empty line between each pair of board configurations. All boards, except for the empty one, will contain exactly one white king and one black king.

Output

For each board configuration read you must output one of the following answers:
Game #d: white king is in check.
Game #d: black king is in check.
Game #d: no king is in check.
where d stands for the game number starting from 1.

Sample Input

..k.....  
ppp.pppp  
........  
.R...B..  
........  
........  
PPPPPPPP  
K.......  

rnbqk.nr  
ppp..ppp  
....p...  
...p....  
.bPP....  
.....N..  
PP..PPPP  
RNBQKB.R  

........  
........  
........  
........  
........  
........  
........  
........

Sample Output

Game #1: black king is in check.  
Game #2: white king is in check.