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
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →
