Cerinta completa
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.
Sample Input 0
1
2 1 1
N B 2
Q B 1
Q A 4
Sample Output 0
YES
Explanation 0
We play games of simplified chess, where the initial piece layout is as follows:
White is the next to move, and they can win the game in move by taking their Knight to and capturing Black’s Queen. Because it took move to win and , we print YES on a new line.
Limbajul de programare folosit: cpp14
Cod:
#include <cstdio>
#include <cstring>
#include <array>
#include <vector>
#include <cstdint>
#include <initializer_list>
using namespace std;
enum Type : char {
None = 0,
Queen = 1,
Rook = 2,
Bishop = 3,
Knight = 4,
Pawn = 5,
King = 6,
TypeSize
};
enum Color : bool {
White = 0,
Black = 1
};
class Piece {
uint8_t type_ : 3;
uint8_t color_ : 1;
public:
Piece()
: type_(None)
, color_()
{
}
Piece(Type type, int row, int col, Color color)
: type_(type)
, color_(color)
{
}
void setType(Type type) {
type_ = type;
}
void clear() {
setType(None);
}
Type type() const {
return Type(type_);
}
Color color() const {
return Color(color_);
}
char toChar() const {
return *reinterpret_cast<const char*>(this);
}
static Piece fromChar(char c) {
return *reinterpret_cast<Piece*>(&c);
}
};
struct Board : public array<array<Piece, 4>, 4> {
static const int Size = 4;
public:
class Iterator {
public:
bool valid() const {
return row_ < Size;
}
const Piece& value() const {
return board_[row_][col_];
}
void next(bool inc = true) {
if (inc)
++col_;
while (row_ < Size) {
while (col_ < Size) {
const auto& piece = board_[row_][col_];
if (piece.type() != None && piece.color() == color_)
return;
++col_;
}
++row_;
col_ = 0;
}
}
int row() const {
return row_;
}
int col() const {
return col_;
}
private:
Iterator(const Board& board, Color color)
: board_(board)
, row_(0)
, col_(0)
, color_(color)
{
next(false);
}
friend class Board;
const Board& board_;
uint8_t row_ : 3;
uint8_t col_ : 3;
uint8_t color_ : 1;
};
public:
bool isValidPostion(int row, int col) const {
return row >= 0 && row < Size && col >= 0 && col < Size;
}
Iterator whiteIterator() const {
return Iterator(*this, White);
}
Iterator blackIterator() const {
return Iterator(*this, Black);
}
bool whiteWins() const {
return !hasQueen(blackIterator());
}
bool blackWins() const {
return !hasQueen(whiteIterator());
}
private:
bool hasQueen(Iterator&& it) const {
while (it.valid()) {
if (it.value().type() == Queen)
return true;
it.next();
}
return false;
}
};
struct Shift {
char x: 4;
char y: 4;
};
vector<Board> generateMoves(const Board::Iterator& it, const Board& board, const initializer_list<Shift>& shifts) {
vector<Board> moves;
moves.reserve(10);
for (const auto& shift : shifts) {
int i = it.row() + shift.x;
int j = it.col() + shift.y;
while (board.isValidPostion(i, j) && (board[i][j].type() == None || board[i][j].color() != it.value().color())) {
moves.push_back(board);
moves.back()[it.row()][it.col()].clear();
moves.back()[i][j] = it.value();
if (board[i][j].type() != None)
break;
else {
i += shift.x;
j += shift.y;
}
}
}
return moves;
}
vector<Board> generatePawnMoves(const Board::Iterator& it, const Board& board) {
vector<Board> moves;
vector<Type> types;
int row = it.row() + (it.value().color() == White ? 1 : -1);
if (row == 0 || row + 1 == board.Size) {
types = { Rook, Bishop, Knight };
}
else {
types = { Pawn };
}
for (int col : { it.col() + -1, it.col() + 1 }) {
if (board.isValidPostion(row, col) &&
board[row][col].type() != None &&
board[row][col].color() == !it.value().color())
{
for (auto t : types) {
moves.push_back(board);
moves.back()[it.row()][it.col()].clear();
moves.back()[row][col] = it.value();
moves.back()[row][col].setType(t);
}
}
}
if (board[row][it.col()].type() == None) {
for (auto t : types) {
moves.push_back(board);
moves.back()[it.row()][it.col()].clear();
moves.back()[row][it.col()] = it.value();
moves.back()[row][it.col()].setType(t);
}
}
return moves;
}
vector<Board> generateMoves(const Board::Iterator& it, const Board& board) {
switch (it.value().type()) {
case Queen:
return generateMoves(it, board, {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}});
case Rook:
return generateMoves(it, board, {{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
case Bishop:
return generateMoves(it, board, {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}});
case Knight:
return generateMoves(it, board, {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}});
case Pawn:
return generatePawnMoves(it, board);
default:
return {};
}
}
void printBoard(const Board& board) {
static char mapping[] = {'*', 'Q', 'R', 'B', 'N', 'P', 'K'};
static_assert(sizeof(mapping) == TypeSize, "Mapping should match in size");
for (int i = 0; i < board.Size; ++i) {
for (int j = 0; j < board.Size; ++j) {
char c = mapping[board[i][j].type()] + ('a' - 'A') * board[i][j].color();
printf("%c", c);
}
printf("\n");
}
}
static_assert(sizeof(Piece) == 1, "Piece size should be one byte");
static_assert(sizeof(Board) == 16, "Board size should be 16 bytes");
Type typeFromChar(char c) {
switch (c) {
case 'Q':
return Queen;
case 'R':
return Rook;
case 'B':
return Bishop;
case 'N':
return Knight;
case 'P':
return Pawn;
case 'K':
return King;
default:
return None;
}
}
bool MinMaxWhiteWins(Color current, const Board& board, int depth) {
if (depth == 0)
return false;
if (current == White) {
auto it = board.whiteIterator();
while (it.valid()) {
for (const auto& next : generateMoves(it, board)) {
if (next.whiteWins() || MinMaxWhiteWins(Black, next, depth - 1))
return true;
}
it.next();
}
return false;
}
else {
auto it = board.blackIterator();
while (it.valid()) {
for (const auto& next : generateMoves(it, board)) {
if (next.blackWins() || !MinMaxWhiteWins(White, next, depth - 1))
return false;
}
it.next();
}
return true;
}
}
void playGame() {
int w, b, d;
scanf("%d %d %d", &w, &b, &d);
Board board;
for (int i = 0; i < w + b; ++i) {
char x, c, r;
scanf(" %c %c %c", &x, &c, &r);
auto t = typeFromChar(x);
c -= 'A';
r -= '1';
board[r][c] = Piece(t, r, c, i < w ? White : Black);
}
bool firstWins = MinMaxWhiteWins(White, board, d);
printf("%s\n", firstWins ? "YES" : "NO");
}
int main() {
int g;
scanf("%d", &g);
while (g--) {
playGame();
}
};
Scor obtinut: 1.0
Submission ID: 464656428
Link challenge: https://www.hackerrank.com/challenges/simplified-chess-engine/problem
Simplified Chess Engine