In this HackerRank Simplified Chess Engine II problem solution we have given M and the layout of pieces for G games, implement a very basic engine for our simplified version of chess that determines whether or not White can win in <= M moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win in <= M moves; otherwise, print NO.
Problem solution in Python.
#!/bin/python3
import math
import os
import random
import re
import sys
def validmoves(piece,posx,posy,whites,blacks,b):
if piece=="R":
L=[]
i=1
while posx+i<4 and not (posx+i,posy) in whites:
L+=[("R",posx+i,posy)]
if (posx+i,posy) in blacks:
break
i+=1
i=1
while posx-i>=0 and not (posx-i,posy) in whites:
L+=[("R",posx-i,posy)]
if (posx-i,posy) in blacks:
break
i+=1
i=1
while posy+i<4 and not (posx,posy+i) in whites:
L+=[("R",posx,posy+i)]
if (posx,posy+i) in blacks:
break
i+=1
i=1
while posy-i>=0 and not (posx,posy-i) in whites:
L+=[("R",posx,posy-i)]
if (posx,posy-i) in blacks:
break
i+=1
return(L)
elif piece=="B":
L=[]
i=1
while posx+i<4 and posy+i<4 and not (posx+i,posy+i) in whites:
L+=[("B",posx+i,posy+i)]
if (posx+i,posy+i) in blacks:
break
i+=1
i=1
while posx-i>=0 and posy+i<4 and not (posx-i,posy+i) in whites:
L+=[("B",posx-i,posy+i)]
if (posx-i,posy+i) in blacks:
break
i+=1
i=1
while posx+i<4 and posy-i>=0 and not (posx+i,posy-i) in whites:
L+=[("B",posx+i,posy-i)]
if (posx+i,posy-i) in blacks:
break
i+=1
i=1
while posx-i>=0 and posy-i>=0 and not (posx-i,posy-i) in whites:
L+=[("B",posx-i,posy-i)]
if (posx-i,posy-i) in blacks:
break
i+=1
return(L)
elif piece=="Q":
return([("Q",z[1],z[2]) for z in validmoves("R",posx,posy,whites,blacks,b)+validmoves("B",posx,posy,whites,blacks,b)])
elif piece=="N":
return([("N",z[0],z[1]) for z in [(posx+2,posy+1),(posx+2,posy-1),(posx+1,posy+2),(posx+1,posy-2),(posx-1,posy+2),(posx-1,posy-2),(posx-2,posy+1),(posx-2,posy-1)] if not z in whites and 0<=z[0]<=3 and 0<=z[1]<=3])
elif piece=="P":
posy+=1-2*b
l=[]
for i in [-1,1]:
if 0<=posx+i<=3 and (posx+i,posy) in blacks:
l+=[(posx+i,posy)]
if not (posx,posy) in whites+blacks:
l+=[(posx,posy)]
if posy in [0,3]:
return([("N",x[0],x[1]) for x in l]+[("B",x[0],x[1]) for x in l]+[("R",x[0],x[1]) for x in l])
else:
return([("P",x[0],x[1]) for x in l])
def simplifiedChessEngine(whites, blacks, moves,b):
if moves==0:
if b:
return("YES")
else:
return("NO")
else:
wh=[(x[1],x[2]) for x in whites]
bl=[(x[1],x[2]) for x in blacks]
i,j=[z[1:] for z in blacks if z[0]=="Q"][0]
l=sum([validmoves(x[0],x[1],x[2],wh,bl,b) for x in whites],[])
if (i,j) in [x[1:] for x in l]:
return("YES")
else:
nextmove=[];nextmove2=[]
for i in range(len(whites)):
for t in validmoves(whites[i][0],whites[i][1],whites[i][2],wh,bl,b):
if (t[1],t[2]) in bl:
nextmove.append((i,t))
else:
nextmove2.append((i,t))
for x in nextmove+nextmove2:
i,t=x[0],x[1]
piece,posx,posy=whites[i]
taken=[z for z in blacks if (z[1],z[2])==t[1:]]
blacks=[z for z in blacks if not z in taken]
whites[i]=t
if simplifiedChessEngine(blacks,whites,moves-1,1-b)=="NO":
whites[i]=(piece,posx,posy)
blacks+=taken
return("YES")
else:
whites[i]=(piece,posx,posy)
blacks+=taken
return("NO")
if __name__ == '__main__':
g = int(input())
for g_itr in range(g):
wbm = input().split()
w = int(wbm[0])
b = int(wbm[1])
m = int(wbm[2])
whites = []
for _ in range(w):
whites.append(input().rstrip().split())
blacks = []
for _ in range(b):
blacks.append(input().rstrip().split())
whites=[[x[0],ord(x[1])-65,int(x[2])-1] for x in whites]
blacks=[[x[0],ord(x[1])-65,int(x[2])-1] for x in blacks]
result = simplifiedChessEngine(whites, blacks, m,0)
print(result)
# Write Your Code HereProblem solution in Java.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class SimplifiedChessEngineII {
static class Piece {
public char type;
public boolean isWhite;
public Piece (char type, boolean isWhite) {
this.type = type;
this.isWhite = isWhite;
}
public Piece (Piece p) {
this.type = p.type;
this.isWhite = p.isWhite;
}
}
static class Board {
public Piece[][] pieces = new Piece[4][4];
public Board(ArrayList<String> w, ArrayList<String> b) {
for (String p : w) {
String[] p3 = p.split(" ");
char type = p3[0].charAt(0);
int x = p3[1].charAt(0)-'A';
int y = p3[2].charAt(0)-'1';
pieces[x][y] = new Piece(type, true);
}
for (String p : b) {
String[] p3 = p.split(" ");
char type = p3[0].charAt(0);
int x = p3[1].charAt(0)-'A';
int y = p3[2].charAt(0)-'1';
pieces[x][y] = new Piece(type, false);
}
}
public Board(Board b) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (b.pieces[i][j] != null)
this.pieces[i][j] = new Piece(b.pieces[i][j]);
}
}
}
public ArrayList<Board> legalMoves(boolean whiteToMove) {
ArrayList<Board> moves = new ArrayList<Board>();
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if (pieces[a][b] != null && pieces[a][b].isWhite == whiteToMove) {
if (pieces[a][b].type == 'P') {
int d = whiteToMove?b+1:b-1;
if (pieces[a][d] == null) {
if (d==0||d==3) {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'R';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'B';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[a][d].type = 'N';
moves.add(newBoard);
}
else {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
for (int c = a-1; c <= a+1; c+=2) {
if (c>=0&&c<4) {
if (pieces[c][d] != null && pieces[c][d].isWhite != whiteToMove) {
if (d==0||d==3) {
Board newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'R';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'B';
moves.add(newBoard);
newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
newBoard.pieces[c][d].type = 'N';
moves.add(newBoard);
}
else {
Board newBoard = new Board(this);
newBoard.pieces[c][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
}
}
}
if (pieces[a][b].type == 'N') {
for (int c = -2; c <= 2; c+=4) {
for (int d = -1; d <= 1; d+=2) {
int e = a+c;
int f = b+d;
int g = a+d;
int h = b+c;
if (e >= 0 && e < 4 && f >= 0 && f < 4) {
if (pieces[e][f] == null || pieces[e][f].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[e][f] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
if (g >= 0 && g < 4 && h >= 0 && h < 4) {
if (pieces[g][h] == null || pieces[g][h].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[g][h] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
}
}
}
}
if (pieces[a][b].type == 'R' || pieces[a][b].type == 'Q') {
for (int c = -1; c <= 1; c += 2) {
for (int d = a+c; d >= 0 && d < 4; d += c) {
if (pieces[d][b] == null || pieces[d][b].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[d][b] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[d][b] != null)
break;
}
for (int d = b+c; d >= 0 && d < 4; d += c) {
if (pieces[a][d] == null || pieces[a][d].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[a][d] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[a][d] != null)
break;
}
}
}
if (pieces[a][b].type == 'B' || pieces[a][b].type == 'Q') {
for (int c = -1; c <= 1; c += 2) {
for (int d = -1; d <= 1; d += 2) {
for (int e = 1; a+e*c >= 0 && a+e*c < 4 && b+e*d >= 0 && b+e*d < 4; e++) {
int f = a+e*c;
int g = b+e*d;
if (pieces[f][g] == null || pieces[f][g].isWhite != whiteToMove) {
Board newBoard = new Board(this);
newBoard.pieces[f][g] = newBoard.pieces[a][b];
newBoard.pieces[a][b] = null;
moves.add(newBoard);
}
if (pieces[f][g] != null)
break;
}
}
}
}
}
}
}
return moves;
}
public boolean doesQueenExist(boolean whiteQueen) {
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if (pieces[a][b] != null && pieces[a][b].type == 'Q' && pieces[a][b].isWhite == whiteQueen)
return true;
}
}
return false;
}
public boolean canCaptureQueen(boolean whiteToMove) {
ArrayList<Board> moves = legalMoves(whiteToMove);
for (Board b : moves) {
if (!b.doesQueenExist(!whiteToMove))
return true;
}
return false;
}
public boolean canReachGoalWhite(int rem) {
if (canCaptureQueen(true))
return true;
if (rem==1)
return false;
ArrayList<Board> moves = legalMoves(true);
for (Board b : moves) {
if (!b.canStopGoalBlack(rem))
return true;
}
return false;
}
public boolean canStopGoalBlack(int rem) {
if (canCaptureQueen(false))
return true;
ArrayList<Board> moves = legalMoves(false);
for (Board b : moves) {
if (!b.canReachGoalWhite(rem-1))
return true;
}
return false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int g = sc.nextInt();
for (int z = 0; z < g; z++) {
int w = sc.nextInt();
int b = sc.nextInt();
int m = (sc.nextInt()+1)/2;
ArrayList<String> wl = new ArrayList<String>();
ArrayList<String> bl = new ArrayList<String>();
sc.nextLine();
for (int i = 0; i < w; i++) {
wl.add(sc.nextLine());
}
for (int i = 0; i < b; i++) {
bl.add(sc.nextLine());
}
Board start = new Board(wl, bl);
System.out.println(start.canReachGoalWhite(m)?"YES":"NO");
}
}
}Problem solution in C++.
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
#include <cctype>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cout << "debug here" << endl;
#define DBGV(vari) cout << #vari<< " = "<< (vari) <<endl;
typedef long long ll;
const int T = 1000;
const int W = 7;
const int M = 6;
const int ROWS = 4;
const int COLS = 4;
string COL_NAMES = "ABCDEFGH";
string COLOR_NAMES = "WB";
#define EMPTY 0
#define QUEEN 1
#define ROOK 2
#define BISHOP 3
#define KNIGHT 4
#define PAWN 5
#define WHITE 0
#define BLACK 1
int codeFigure(char color, char type)
{
int code;
if(type == 'Q') code = QUEEN;
else if(type == 'R') code = ROOK;
else if(type == 'B') code = BISHOP;
else if(type == 'N') code = KNIGHT;
else if(type == 'P') code = PAWN;
else assert(false);
if(color == 'W') code *= 2;
else if(color == 'B') code = 2 * code + 1;
else assert(false);
return code;
}
int codeFigureFromInts(int color, int type)
{
return 2 * type + color;
}
char figureToChar(int figure)
{
if(figure == EMPTY) return '*';
int color = figure % 2;
int type = figure / 2;
if(type == QUEEN) return (color == WHITE) ? 'Q' : 'q';
else if(type == ROOK) return (color == WHITE) ? 'R' : 'r';
else if(type == BISHOP) return (color == WHITE) ? 'B' : 'b';
else if(type == KNIGHT) return (color == WHITE) ? 'N' : 'n';
else if(type == PAWN) return (color == WHITE) ? 'P' : 'p';
assert(false);
}
int getColor(int figure)
{
assert(figure != EMPTY);
return figure % 2;
}
int getType(int figure) { return figure / 2; }
int oppositeColor(int color) { return 1 - color; }
typedef vector<vi> Board;
void printBoard(Board board)
{
cout << " A B C D E F G H" << endl;
REPD(i, ROWS - 1, 0)
{
cout << i << " | ";
REP(j, 0, COLS - 1)
{
cout << figureToChar(board[i][j]) << " ";
}
cout << endl;
}
}
vector<pii> getStraightMoves(pii pos, Board& board)
{
vector<pii> res;
REP(i, pos.fi + 1, ROWS - 1)
{
auto p = mp(i, pos.se);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
REPD(i, pos.fi -1, 0)
{
auto p = mp(i, pos.se);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
REP(j, pos.se + 1, COLS - 1)
{
auto p = mp(pos.fi, j);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
REPD(j, pos.se - 1, 0)
{
auto p = mp(pos.fi, j);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
}
return res;
}
vector<pii> getDiagonalMoves(pii pos, Board& board)
{
vector<pii> res;
int r = pos.fi + 1;
int c = pos.se + 1;
while(r < ROWS && c < COLS)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
++r;
++c;
}
r = pos.fi - 1;
c = pos.se - 1;
while(r >= 0 && c >= 0)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
--r;
--c;
}
r = pos.fi + 1;
c = pos.se - 1;
while(r < ROWS && c >= 0)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
++r;
--c;
}
r = pos.fi - 1;
c = pos.se + 1;
while(r >= 0 && c < COLS)
{
auto p = mp(r, c);
res.pb(p);
if(board[p.fi][p.se] != EMPTY) break;
--r;
++c;
}
return res;
}
bool onBoard(pii pos)
{
return pos.fi >= 0 && pos.fi < ROWS && pos.se >= 0 && pos.se < COLS;
}
vector<pii> getPawnMoves(pii pos, Board& board)
{
int color = getColor(board[pos.fi][pos.se]);
int row = (color == WHITE) ? pos.fi + 1 : pos.fi - 1;
vector<pii> res;
auto p = mp(row, pos.se);
if(onBoard(p) && board[p.fi][p.se] == EMPTY)
{
res.pb(p);
}
p = mp(row, pos.se - 1);
if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se]))
{
res.pb(p);
}
p = mp(row, pos.se + 1);
if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se]))
{
res.pb(p);
}
return res;
}
vector<pii> getKnightMoves(pii pos)
{
vector<pii> res;
int r, c;
int rs[] = {1, 2,2,1,-1,-2,-2,-1};
int cs[] = {-2,-1,1,2, 2, 1,-1,-2};
FOR(i, 8)
{
r = pos.fi + rs[i];
c = pos.se + cs[i];
auto p = mp(r, c);
if(onBoard(p)) res.pb(p);
}
return res;
}
vector<pii> getMoves(int figureType, pii pos, Board& board)
{
vector<pii> res;
vector<pii> tmp;
switch(figureType)
{
case QUEEN:
res = getStraightMoves(pos, board);
tmp = getDiagonalMoves(pos, board);
FOR(i, SZ(tmp)) res.pb(tmp[i]);
break;
case BISHOP:
res = getDiagonalMoves(pos, board);
break;
case ROOK:
res = getStraightMoves(pos, board);
break;
case KNIGHT:
res = getKnightMoves(pos);
break;
case PAWN:
res = getPawnMoves(pos, board);
break;
default:
cout << "! " << figureType << endl;
assert(false);
}
return res;
}
int solve(int colorToMove, Board board, int remainingMoves)
{
if(remainingMoves == 0) return BLACK;
vector<Board> newBoards;
vector<pii> positions;
FOR(i, ROWS) FOR(j, COLS) if(board[i][j] != EMPTY && getColor(board[i][j]) == colorToMove) positions.pb(mp(i, j));
FOR(k, positions.size())
{
auto pos = positions[k];
auto moves = getMoves(getType(board[pos.fi][pos.se]), pos, board);
FOR(j, moves.size())
{
auto p = moves[j];
if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == colorToMove) continue;
if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == oppositeColor(colorToMove) && getType(board[p.fi][p.se]) == QUEEN)
{
return colorToMove;
}
if(board[p.fi][p.se] == EMPTY || getColor(board[p.fi][p.se]) == oppositeColor(colorToMove))
{
if(getType(board[pos.fi][pos.se]) == PAWN && ((colorToMove == WHITE && p.fi == ROWS - 1) || (colorToMove == BLACK && p.fi == 0)))
{
auto newBoard = board;
newBoard[pos.fi][pos.se] = EMPTY;
newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, BISHOP);
newBoards.pb(newBoard);
newBoard = board;
newBoard[pos.fi][pos.se] = EMPTY;
newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, KNIGHT);
newBoards.pb(newBoard);
newBoard = board;
newBoard[pos.fi][pos.se] = EMPTY;
newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, ROOK);
newBoards.pb(newBoard);
}
else
{
auto newBoard = board;
newBoard[pos.fi][pos.se] = EMPTY;
newBoard[p.fi][p.se] = board[pos.fi][pos.se];
newBoards.pb(newBoard);
}
}
}
}
for(int i = 0; i < newBoards.size(); ++i)
{
int res = solve(oppositeColor(colorToMove), newBoards[i], remainingMoves - 1);
if(res == colorToMove) return colorToMove;
}
return oppositeColor(colorToMove);
}
int main()
{
ios_base::sync_with_stdio(0);
int tests;
cin >> tests;
assert(tests >= 1 && tests <= T);
while(tests--)
{
int w, b, m;
cin >> w >> b >> m;
assert(w >= 1 && w <= W);
assert(b >= 1 && b <= W);
assert(m >= 1 && m <= M);
Board board = vector<vi> (ROWS, vi(COLS, EMPTY));
set<pii> positions;
FOR(i, w + b)
{
char type;
char column;
int row;
cin >> type >> column >> row;
char color = (i < w) ? 'W' : 'B';
int figure = codeFigure(color, type);
if(type == 'P')
{
if(color == 'W') assert(row != ROWS);
else if(color == 'B') assert(row != 1);
}
int found = 0;
FOR(j, COLS) if(column == COL_NAMES[j]) found = 1;
assert(found);
assert(row >= 1 && row <= ROWS);
auto pos = mp(row - 1, (int)(column - 'A'));
board[pos.fi][pos.se] = figure;
positions.insert(pos);
}
assert(positions.size() == w + b);
int res = solve(WHITE, board, m);
if(res == WHITE) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}Problem solution in C.
#include <stdio.h>
#include <string.h>
#define QUEEN 1
#define KNIGHT 2
#define BISHOP 3
#define ROOK 4
#define PAWN 5
#define BOUND 8
int m;
unsigned char __board[8][8];
unsigned char *_board[8]={__board[0]+2, __board[1]+2, __board[2]+2, __board[3]+2,
__board[4]+2, __board[5]+2, __board[6]+2, __board[7]+2};
unsigned char **board=_board+2;
unsigned char black[4][4];
int pl[2]={1, -1};
int moves[6][10][3]={
{},
{ {-1, -1, 3}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1} },
{ {-2, -1, 1}, {-2, 1},
{-1, -2}, {-1, 2},
{1, -2}, {1, 2},
{2, -1}, {2, 1} },
{ {-1, -1, 3}, {-1, 1},
{1, -1}, {1, 1} },
{ {-1, 0, 3},
{0, -1}, {0, 1},
{1, 0} },
{ {-1, 0, 1}, {-1, -1}, {-1, 1},
{0, 0},
{1, 0}, {1, 1}, {1, -1} }
};
static int min(int a, int b) {
return a<b?a:b;
}
static int max(int a, int b) {
return a>b?a:b;
}
void init_game(void) {
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
__board[i][j]=(BOUND+1)*(!(1<i && i<6 && 1<j && j<6));
memset(black, 0, sizeof(black));
}
void print_board(void) {
int i, j;
char fc[6]={'=', 'Q', 'N', 'B', 'R', 'P'};
for (i=0; i<4; i++, printf("\n"))
for (j=0; j<4; j++)
printf("%c ", fc[board[i][j]]+('a'-'A')*black[i][j]);
printf("\n");
}
int solve(int mv) {
int i, j, k, d, b=mv&1;
int ni, nj, t, tb, r, mm=pl[!b], prom[5]={0, 0, 0, 0, 0}, p;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1; d<=moves[board[i][j]][0][2]; d++) {
if (board[i][j]!=PAWN || k) {
if (board[i][j]==PAWN)
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
else
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t) {
if (t>BOUND)
break;
else if (t==QUEEN && black[ni][nj]!=b)
return pl[b];
break;
}
}
}
}
}
}
}
if ((mv+1)==m)
return 0;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1, t=0; d<=moves[board[i][j]][0][2] && !t; d++) {
prom[0]=board[i][j]; prom[1]=board[i][j]; prom[2]=0;
if (board[i][j]==PAWN) {
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
if (k) {
if (t==0 || t>BOUND || black[ni][nj]==b)
break;
} else if (t)
break;
if ((ni==0 && !b) || (ni==3 && b)) {
prom[1]=KNIGHT; prom[2]=BISHOP; prom[3]=ROOK; prom[4]=0;
}
} else {
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t>BOUND || (t && black[ni][nj]==b))
break;
}
for (p=1; prom[p]; p++) {
tb=black[ni][nj];
board[ni][nj]=prom[p];
black[ni][nj]=b;
board[i][j]=0;
black[i][j]=0;
r=solve(mv+1);
board[i][j]=prom[0];
board[ni][nj]=t;
black[i][j]=b;
black[ni][nj]=tb;
if (r==pl[b])
return r;
else if (b)
mm=min(mm, r);
else
mm=max(mm, r);
}
}
}
}
}
}
return mm;
}
int main(void) {
int i, j, g, r, b, w;
char figuremap[26]={['Q'-'A']=QUEEN, ['N'-'A']=KNIGHT, ['B'-'A']=BISHOP,
['R'-'A']=ROOK, ['P'-'A']=PAWN};
char t, c;
scanf("%d", &g);
for (i=0; i<g; i++) {
init_game();
scanf("%d%d%d\n", &w, &b, &m);
for (j=0; j<w; j++) {
scanf("%c %c %d\n", &t, &c, &r);
board[4-r][c-'A']=figuremap[t-'A'];
}
for (j=0; j<b; j++) {
scanf("%c %c %d\n", &t, &c, &r);
r=4-r; c-='A';
board[r][c]=figuremap[t-'A'];
black[r][c]=1;
}
printf("%s\n", solve(0)==1?"YES":"NO");
}
return 0;
}
0 Comments