Simplified Chess Engine
Problem Statement :
Chess is a very popular game played by hundreds of millions of people. Nowadays, we have chess engines such as Stockfish and Komodo to help us analyze games. These engines are very powerful pieces of well-developed software that use intelligent ideas and algorithms to analyze positions and sequences of moves, as well as find tactical ideas. Consider the following simplified version of chess: Board: It's played on a board between two players named Black and White. Pieces and Movement: White initially has pieces and Black initially has pieces. There are no Kings and no Pawns on the board. Each player has exactly one Queen, at most two Rooks, and at most two minor pieces (i.e., a Bishop and/or Knight). Each piece's possible moves are the same as in classical chess, and each move made by any player counts as a single move. There is no draw when positions are repeated as there is in classical chess. Objective: The goal of the game is to capture the opponent’s Queen without losing your own. Given and the layout of pieces for games of simplified chess, implement a very basic (in comparison to the real ones) engine for our simplified version of chess with the ability to determine whether or not White can win in moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win under the specified conditions; otherwise, print NO. Input Format The first line contains a single integer, , denoting the number of simplified chess games. The subsequent lines define each game in the following format: The first line contains three space-separated integers denoting the respective values of (the number of White pieces), (the number of Black pieces), and (the maximum number of moves we want to know if White can win in). The subsequent lines describe each chesspiece in the format t c r, where is a character denoting the type of piece (where is Queen, is Knight, is Bishop, and is Rook), and and denote the respective column and row on the board where the figure is placed (where and ). These inputs are given as follows: Each of the subsequent lines denotes the type and location of a White piece on the board. Each of the subsequent lines denotes the type and location of a Black piece on the board. Constraints It is guaranteed that the locations of all pieces given as input are distinct. Each player initially has exactly one Queen, at most two Rooks and at most two minor pieces. Output Format For each of the games of simplified chess, print whether or not White can win in moves on a new line. If it's possible, print YES; otherwise, print NO.
Solution :
Solution in C :
In C :
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct State State;
typedef struct {
State **data;
int count;
int capacity;
} List;
List *list_create(int capacity) {
List *list = (List *)malloc(sizeof(List));
list->capacity = (capacity > 0) ? capacity : 8;
list->count = 0;
list->data = (State **)malloc(list->capacity*sizeof(State *));
assert(list->data);
return list;
}
void list_destroy(List *list) {
if (list && list->data) {
for (int i = 0; i < list->count; i++) free(list->data[i]);
free(list->data);
}
free(list);
}
void list_append(List *list, State *item) {
if (list->count >= list->capacity) {
list->capacity = 1.5*list->capacity + 1;
list->data = (State **)realloc(list->data, list->capacity*sizeof(State *));
assert(list->data);
}
list->data[list->count++] = item;
}
/**********************************************************************/
#define TURN_WHITE 0
#define TURN_BLACK 1
#define PIECE_NONE 0
#define COLOR_MASK 0xf0
#define PIECE_MASK 0x0f
#define QUEEN 0x01
#define ROOK 0x02
#define BISHOP 0x03
#define KNIGHT 0x04
#define COLOR_WHITE 0x10
#define WHITE_QUEEN 0x11
#define WHITE_ROOK 0x12
#define WHITE_BISHOP 0x13
#define WHITE_KNIGHT 0x14
#define COLOR_BLACK 0x20
#define BLACK_QUEEN 0x21
#define BLACK_ROOK 0x22
#define BLACK_BISHOP 0x23
#define BLACK_KNIGHT 0x24
struct State {
char turn;
unsigned char board[4][4];
};
State *state_new(void) {
State *s = (State *)malloc(sizeof(State));
s->turn = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
s->board[i][j] = PIECE_NONE;
}
}
return s;
}
State *state_copy(State *orig) {
State *copy = (State *)malloc(sizeof(State));
copy->turn = orig->turn;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
copy->board[i][j] = orig->board[i][j];
}
}
return copy;
}
State *move_piece(State *orig, int i0, int j0, int i1, int j1) {
State *copy = state_copy(orig);
copy->turn++;
copy->board[i1][j1] = copy->board[i0][j0];
copy->board[i0][j0] = 0;
return copy;
}
// Returns 1 if winning state for white (meaning black queen has been captured).
// Returns -1 if winning state for black (meaning white queen has been captured).
// Returns 0 for any other state.
int state_utility(State *s) {
int whiteQueen = 0, blackQueen = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (s->board[i][j] == WHITE_QUEEN) {
whiteQueen = 1;
if (blackQueen) return 0;
} else if (s->board[i][j] == BLACK_QUEEN) {
blackQueen = 1;
if (whiteQueen) return 0;
}
}
}
if (whiteQueen && !blackQueen) return 1;
if (!whiteQueen && blackQueen) return -1;
return 0;
}
void state_print(State *s) {
if (s->turn % 2 == 0) printf("---white's turn (%d)---\n", s->turn);
else printf("---black's turn (%d)---\n", s->turn);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
unsigned char piece = s->board[i][j];
if (!piece) printf(". ");
else if (piece == WHITE_QUEEN) printf("Q ");
else if (piece == WHITE_ROOK) printf("R ");
else if (piece == WHITE_BISHOP) printf("B ");
else if (piece == WHITE_KNIGHT) printf("N ");
else if (piece == BLACK_QUEEN) printf("q ");
else if (piece == BLACK_ROOK) printf("r ");
else if (piece == BLACK_BISHOP) printf("b ");
else if (piece == BLACK_KNIGHT) printf("n ");
else printf("? ");
}
printf("\n");
}
}
List *get_successors(State *s) {
int color = (s->turn % 2 == 0) ? COLOR_WHITE : COLOR_BLACK;
List *list = list_create(37);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
unsigned char piece = s->board[i][j];
if ((piece & COLOR_MASK) != color) continue;
if ((piece & PIECE_MASK) == QUEEN) {
for (int ii = i-1; ii >= 0; ii--) {
if ((s->board[ii][j] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][j];
State *new = move_piece(s, i, j, ii, j);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1; ii < 4; ii++) {
if ((s->board[ii][j] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][j];
State *new = move_piece(s, i, j, ii, j);
list_append(list, new);
if (prev) break;
}
for (int jj = j-1; jj >= 0; jj--) {
if ((s->board[i][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[i][jj];
State *new = move_piece(s, i, j, i, jj);
list_append(list, new);
if (prev) break;
}
for (int jj = j+1; jj < 4; jj++) {
if ((s->board[i][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[i][jj];
State *new = move_piece(s, i, j, i, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
} else if ((piece & PIECE_MASK) == ROOK) {
for (int ii = i-1; ii >= 0; ii--) {
if ((s->board[ii][j] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][j];
State *new = move_piece(s, i, j, ii, j);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1; ii < 4; ii++) {
if ((s->board[ii][j] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][j];
State *new = move_piece(s, i, j, ii, j);
list_append(list, new);
if (prev) break;
}
for (int jj = j-1; jj >= 0; jj--) {
if ((s->board[i][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[i][jj];
State *new = move_piece(s, i, j, i, jj);
list_append(list, new);
if (prev) break;
}
for (int jj = j+1; jj < 4; jj++) {
if ((s->board[i][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[i][jj];
State *new = move_piece(s, i, j, i, jj);
list_append(list, new);
if (prev) break;
}
} else if ((piece & PIECE_MASK) == BISHOP) {
for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
if ((s->board[ii][jj] & COLOR_MASK) == color) break;
unsigned char prev = s->board[ii][jj];
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
if (prev) break;
}
} else if ((piece & PIECE_MASK) == KNIGHT) {
int moves[8][2] = {{-2,-1}, {-2,1}, {2,-1}, {2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}};
for (int k = 0; k < 8; k++) {
int ii = i + moves[k][0], jj = j + moves[k][1];
if (ii < 0 || ii >= 4 || jj < 0 || jj >= 4) continue; // stay within board
if ((s->board[ii][jj] & COLOR_MASK) == color) continue; // can't capture own pieces
State *new = move_piece(s, i, j, ii, jj);
list_append(list, new);
}
}
}
}
return list;
}
int minimax_value(State *s, int maxPly) {
int u = state_utility(s);
if (u != 0 || s->turn >= maxPly) return u;
if (s->turn % 2 == 0) { // white's turn to move
int maxValue = -100;
List *list = get_successors(s);
for (int i = 0; i < list->count; i++) {
int v = minimax_value(list->data[i], maxPly);
if (v > maxValue) {
maxValue = v;
if (maxValue == 1) break; // can't do any better.
}
}
list_destroy(list);
return maxValue;
} else { // black's turn to move
int minValue = 100;
List *list = get_successors(s);
for (int i = 0; i < list->count; i++) {
int v = minimax_value(list->data[i], maxPly);
if (v < minValue) {
minValue = v;
if (minValue == -1) break; // can't do any better
}
}
list_destroy(list);
return minValue;
}
}
int main(void) {
int g, w, b, m;
scanf("%d", &g);
while (g--) {
scanf("%d %d %d", &w, &b, &m);
State *s = state_new();
for (int i = 0; i < w; i++) {
char t, c, r;
scanf(" %c %c %c", &t, &c, &r);
int i = r-'1', j = c-'A';
if (t == 'Q') s->board[i][j] = WHITE_QUEEN;
else if (t == 'R') s->board[i][j] = WHITE_ROOK;
else if (t == 'B') s->board[i][j] = WHITE_BISHOP;
else if (t == 'N') s->board[i][j] = WHITE_KNIGHT;
else assert(0);
}
for (int i = 0; i < b; i++) {
char t, c, r;
scanf(" %c %c %c", &t, &c, &r);
int i = r-'1', j = c-'A';
if (t == 'Q') s->board[i][j] = BLACK_QUEEN;
else if (t == 'R') s->board[i][j] = BLACK_ROOK;
else if (t == 'B') s->board[i][j] = BLACK_BISHOP;
else if (t == 'N') s->board[i][j] = BLACK_KNIGHT;
else assert(0);
}
if (m % 2 == 0) m--;
if (minimax_value(s, m) == 1) printf("YES\n");
else printf("NO\n");
free(s);
}
return 0;
}
Solution in C++ :
In C ++ :
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i < int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define x first
#define y second
template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));
const int N = 4;
int a[N][N];
int w, b, m;
inline int getId (const char& c)
{
if (c == 'Q')
return 1;
if (c == 'N')
return 2;
if (c == 'B')
return 3;
if (c == 'R')
return 4;
throw;
}
inline bool read()
{
if (scanf ("%d%d%d", &w, &b, &m) != 3)
return false;
memset(a, 0, sizeof a);
forn (i, w)
{
char c;
char x;
int y;
assert(scanf (" %c %c%d", &c, &x, &y) == 3);
a[x - 'A'][y - 1] = getId(c);
}
forn (i, b)
{
char c;
char x;
int y;
assert(scanf (" %c %c%d", &c, &x, &y) == 3);
a[x - 'A'][y - 1] = -getId(c);
}
return true;
}
map<li, char> d[20];
const int P = 1009;
const int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};
const int dx2[8] = {1, 2, 1, 2, -1, -2, -1, -2};
const int dy2[8] = {2, 1, -2, -1, 2, 1, -2, -1};
inline bool valid (int x, int y)
{
return x >= 0 && y >= 0 && x < 4 && y < 4;
}
int calc (int h, int m)
{
if (m == 0)
return 0;
li hash = h;
forn (i, 4)
forn (j, 4)
hash = hash * P + a[i][j];
if (d[m].count(hash))
return d[m][hash];
if (h == 0)
{
forn (x, 4)
forn (y, 4)
{
if (a[x][y] <= 0)
continue;
if (a[x][y] == 1)
{
forn (k, 8)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] <= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == -1 || calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 1;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
if (a[x][y] == 2)
{
forn (k, 8)
{
int nx = x + dx2[k], ny = y + dy2[k];
if (!valid(nx, ny) || a[nx][ny] > 0)
continue;
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == -1 || calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 1;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
}
}
if (a[x][y] == 3)
{
fore (k, 4, 8)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] <= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == -1 || calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 1;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
if (a[x][y] == 4)
{
forn (k, 4)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] <= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == -1 || calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 1;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
}
return d[m][hash] = 0;
}
else
{
forn (x, 4)
forn (y, 4)
{
if (a[x][y] >= 0)
continue;
if (a[x][y] == -1)
{
forn (k, 8)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] >= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == 1 || !calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 0;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
if (a[x][y] == -2)
{
forn (k, 8)
{
int nx = x + dx2[k], ny = y + dy2[k];
if (!valid(nx, ny) || a[nx][ny] < 0)
continue;
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == 1 || !calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 0;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
}
}
if (a[x][y] == -3)
{
fore (k, 4, 8)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] >= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == 1 || !calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 0;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
if (a[x][y] == -4)
{
forn (k, 4)
{
int nx = x + dx[k], ny = y + dy[k];
while (valid(nx, ny) && a[nx][ny] >= 0)
{
int old = a[nx][ny];
a[nx][ny] = a[x][y];
a[x][y] = 0;
if (old == 1 || !calc(h ^ 1, m - 1))
{
a[x][y] = a[nx][ny];
a[nx][ny] = old;
return d[m][hash] = 0;
}
a[x][y] = a[nx][ny];
a[nx][ny] = old;
if (a[nx][ny] != 0)
break;
nx += dx[k], ny += dy[k];
}
}
}
}
return d[m][hash] = 1;
}
}
inline void solve()
{
forn (i, m + 1)
d[i].clear();
int ans = calc(0, m);
//cerr << ans << endl;
if (ans)
puts("YES");
else
puts("NO");
}
int main()
{
#ifdef SU2_PROJ
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
cout << setprecision(25) << fixed;
cerr << setprecision(10) << fixed;
srand(int(time(NULL)));
int testCnt;
assert(scanf ("%d", &testCnt) == 1);
forn (test, testCnt)
{
assert(read());
solve();
}
#ifdef SU2_PROJ
cerr << "TIME: " << clock() << endl;
#endif
return 0;
}
Solution in Java :
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static int[] queen = { 1, 0, -1, 0, 0, 1, 0, -1, 2, 0, -2, 0, 0, 2, 0, -2, 3, 0, -3, 0, 0, 3, 0, -3, 1, 1,
-1, -1, 1, -1, -1, 1, 2, 2, -2, -2, 2, -2, -2, 2, 3, 3, -3, -3, 3, -3, -3, 3 };
public static int[] rook = { 1, 0, -1, 0, 0, 1, 0, -1, 2, 0, -2, 0, 0, 2, 0, -2, 3, 0, -3, 0, 0, 3, 0, -3 };
public static int[] bishop = { 1, 1, -1, -1, 1, -1, -1, 1, 2, 2, -2, -2, 2, -2, -2, 2, 3, 3, -3, -3, 3, -3, -3, 3 };
public static int[] knight = { 1, 2, -1, -2, 2, 1, -2, -1, 1, -2, -1, 2, 2, -1, -2, 1 };
public abstract static class Piece
{
final boolean white;
final int[] moves;
final boolean canJump;
int x, y;
boolean taken;
public Piece(int x, int y, boolean white, int[] moves, boolean canJump)
{
this.white = white;
this.x = x;
this.y = y;
this.moves = moves;
this.canJump = canJump;
}
int count()
{
return moves.length / 2;
}
boolean canMove(int number, Piece[][] board)
{
int dx = moves[2 * number];
int dy = moves[2 * number + 1];
int x = this.x + dx;
int y = this.y + dy;
if (!(0 <= x && x <= 3 && 0 <= y && y <= 3))
{
return false;
}
Piece taking = board[x][y];
if (taking != null && taking.white == white)
{
return false;
}
if (canJump)
{
return true;
}
int steps = Math.max(Math.abs(dx), Math.abs(dy)) - 1;
int sx = dx == 0 ? 0 : dx > 0 ? 1 : -1;
int sy = dy == 0 ? 0 : dy > 0 ? 1 : -1;
for (int i = 1; i <= steps; i++)
{
if (board[this.x + sx * i][this.y + sy * i] != null)
{
return false;
}
}
return true;
}
void move(int number, boolean reverse)
{
number += !reverse ? 0 : number % 2 == 0 ? 1 : -1;
this.x += moves[2 * number];
this.y += moves[2 * number + 1];
}
@Override
public String toString()
{
return (white ? "white " : "black ") + getClass().getSimpleName();
}
}
public static class Queen extends Piece
{
public Queen(int x, int y, boolean white)
{
super(x, y, white, queen, false);
}
}
public static class Rook extends Piece
{
public Rook(int x, int y, boolean white)
{
super(x, y, white, rook, false);
}
}
public static class Bishop extends Piece
{
public Bishop(int x, int y, boolean white)
{
super(x, y, white, bishop, false);
}
}
public static class Knight extends Piece
{
public Knight(int x, int y, boolean white)
{
super(x, y, white, knight, true);
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int games = sc.nextInt();
while (games-- > 0)
{
int w = sc.nextInt();
int b = sc.nextInt();
int m = sc.nextInt();
Piece board[][] = new Piece[4][4];
List<Piece> white = new ArrayList<>();
List<Piece> black = new ArrayList<>();
for (int j = 0; j < 2; j++)
{
for (int i = 0; i < (j == 0 ? w : b); i++)
{
char p = sc.next()
.charAt(0);
int x = sc.next()
.charAt(0) - 'A';
int y = sc.nextInt() - 1;
Piece piece = p == 'Q' ? new Queen(x, y, j == 0)
: p == 'R' ? new Rook(x, y, j == 0)
: p == 'B' ? new Bishop(x, y, j == 0) : new Knight(x, y, j == 0);
board[x][y] = piece;
(j == 0 ? white : black).add(piece);
}
}
boolean win = move(true, white, black, board, m);
System.out.println(win ? "YES" : "NO");
}
}
public static boolean move(boolean whiteTurn, List<Piece> white, List<Piece> black, Piece[][] board, int m)
{
if (m <= 0)
{
return false;
}
boolean all = !whiteTurn;
List<Piece> pieces = whiteTurn ? white : black;
for (Piece piece : pieces)
{
if (piece.taken)
{
continue;
}
for (int i = 0; i < piece.count(); i++)
{
if (piece.canMove(i, board))
{
board[piece.x][piece.y] = null;
piece.move(i, false);
Piece taken = board[piece.x][piece.y];
board[piece.x][piece.y] = piece;
if (taken != null)
{
taken.taken = true;
}
try
{
if (taken instanceof Queen)
{
return whiteTurn;
}
boolean result = move(!whiteTurn, white, black, board, m - 1);
if (result && whiteTurn)
{
return true;
}
all &= result;
}
finally
{
if (taken != null)
{
taken.taken = false;
}
board[piece.x][piece.y] = taken;
piece.move(i, true);
board[piece.x][piece.y] = piece;
}
}
}
}
return all;
}
}
Solution in Python :
In Python3 :
N = 4
D = ((1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))
FIGURES = "QNBR"
RANGE = ((0, 8), (8, 16), (4, 8), (0, 4))
def solve():
w, b, m = map(int, input().split())
m -= (m + 1) % 2
field = [[0] * N for _ in range(N)]
for i in range(w + b):
figure, col, row = input().split()
col = ord(col) - ord('A')
row = int(row) - 1
figure = FIGURES.find(figure) + 1
if i >= w:
figure *= -1
field[row][col] = figure
return search(tuple(map(tuple, field)), m)
def search(field, m):
if (field, m) in memo:
return memo[(field, m)]
white = (m % 2 == 1)
for i in range(N):
for j in range(N):
f = field[i][j]
if f == 0 or ((f > 0) != white):
continue
for d in range(*RANGE[abs(f) - 1]):
dx, dy = D[d]
x, y = i, j
while True:
x += dx
y += dy
if x < 0 or x >= N or y < 0 or y >= N:
break
g = field[x][y]
if g != 0 and (g > 0) == (f > 0):
break
if abs(g) == 1:
memo[(field, m)] = white
return white
if m > 1:
new = list(map(list, field))
new[i][j] = 0
new[x][y] = f
new = tuple(map(tuple, new))
s = search(new, m - 1)
if white == s:
memo[(field, m)] = s
return s
if g:
break
memo[(field, m)] = not white
return not white
memo = {}
for _ in range(int(input())):
print("YES" if solve() else "NO")
View More Similar Problems
Game of Two Stacks
Alexa has two stacks of non-negative integers, stack A = [a0, a1, . . . , an-1 ] and stack B = [b0, b1, . . . , b m-1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game: In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified f
View Solution →Largest Rectangle
Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed. There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join adjacent buildings, they will form a solid rectangle
View Solution →Simple Text Editor
In this challenge, you must implement a simple text editor. Initially, your editor contains an empty string, S. You must perform Q operations of the following 4 types: 1. append(W) - Append W string to the end of S. 2 . delete( k ) - Delete the last k characters of S. 3 .print( k ) - Print the kth character of S. 4 . undo( ) - Undo the last (not previously undone) operation of type 1 or 2,
View Solution →Poisonous Plants
There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plan
View Solution →AND xor OR
Given an array of distinct elements. Let and be the smallest and the next smallest element in the interval where . . where , are the bitwise operators , and respectively. Your task is to find the maximum possible value of . Input Format First line contains integer N. Second line contains N integers, representing elements of the array A[] . Output Format Print the value
View Solution →Waiter
You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the
View Solution →