题目大意：（好长的题啊……先赞一个！）二人对弈，白先黑后，棋盘固定8*8，白黑双方各执一子，白子曰白王（White King），黑子曰黑卒（Black Pawn）。棋盘上除了空格区域.外还有两种区域，一种是D（Dangerous），另一种是F（Forbidden），规定F区两种棋都不能进入，D区只有白棋不能进入。再来说一下走法，白棋可以往邻接的8个方向走，而黑棋只能往正下方一个方向走。求哪一方赢并输出，所以要说一下胜利标准，白棋的目标是要抓到黑棋，如果白棋走到黑棋占据的格子里，白棋就赢了；任意一方如果走投无路了（轮到它走但它没法走了）另一方就赢了，如果黑棋已经走到最底层又轮到它走了，黑棋就赢了。还有一个比较有意思的point，黑棋的左下和右下两个格子总有两块D（卒前侍卫），它们是跟着黑棋走的。
题目分析：（在此提醒白先黑后，一步一步走）读懂题意其实就胜利了30%了，首先确定用BFS，然后分析一下胜利条件里的“走投无路”，只要白棋不是初始点周围围了8个不可走区域，它就不可能走投无路；黑棋的情况稍微复杂，如果黑棋的下方是F或白棋，黑棋就走投无路了。另外注意一下坑跌的输入，白棋和黑棋的位置输入之后要记得处理一下的。分析就到此为止了。
实现思路：说一下我是怎么实现的。以白棋为起点开始BFS，黑棋的当前位置x是黑棋的初始位置x+白棋的当前步数-1，y总是不变的，两个“卒前侍卫”的位置也容易推。剩下的都在代码里了。
code:
#includePS：好艰辛啊，被黑棋被白棋堵死这一种情况wrong了n+1次……#include #include #include using namespace std; char map[10][10],vis[10][10][10]; int px,py,dir[8][2]= {1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1}; struct node { int x,y,step; }first,next; bool judge(node a) { if(a.x==px+a.step&&(a.y==py+1||a.y==py-1))return false; if(map[a.x][a.y]=='F'||map[a.x][a.y]=='D')return false; return a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y][a.step]; } bool bfs(int kx,int ky) { queue q; vis[kx][ky][0]=true; first.x=kx,first.y=ky,first.step=0; q.push(first); while(!q.empty()) { //printf(白在：%d,%d,step==%d ,first.x,first.y,first.step); first=q.front(); q.pop(); if(map[px+first.step][py]=='F') { //printf(黑被挡住了 ); return true; } if(px+first.step>7) { //printf(黑到底了 ); return false; } for(int i=0; i<8; i++) { next.x=first.x+dir[i][0]; next.y=first.y+dir[i][1]; next.step=first.step+1; if(judge(next)) { vis[next.x][next.y][next.step]=true; if(next.x==px+first.step&&next.y==py||next.x==px+next.step&&next.y==py) {//黑被抓住||黑被白堵死而走投无路 //printf(黑%d,%d被抓住了,%d,%d ,px+first.step,py,first.x,first.y); return true; } q.push(next); } } } //printf(over ); return false; } int main() { int i,kx,ky,t; //freopen(1.txt,r,stdin); scanf(%d,&t); while(t--) { memset(vis,false,sizeof(vis)); for(i=0; i<8; i++) { scanf(%s,map[i]); } scanf(%d%d,&kx,&ky); scanf(%d%d,&px,&py); i=8-py; py=px-1; px=i; //printf(kx==%d,ky==%d,px==%d,py==%d ,8-ky,kx-1,px,py); if(bfs(8-ky,kx-1))printf(White ); else printf(Black ); } return 0; }
