Simplified Chess Engine II – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

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 to find tactical ideas. Consider the following simplified version of chess:

Board:
- It’s played on a board between two players named Black and White.
- Rows are numbered from to , where the top row is and the bottom row is .
- Columns are lettered from to , where the leftmost column is and the rightmost column is .
Pieces and Movement:
- White initially has pieces and Black initially has pieces.
- There are no Kings on the board. Each player initially has exactly Queen, at most Pawns, at most Rooks, and at most minor pieces (i.e., a Bishop and/or Knight).
- White‘s Pawns move up the board, while Black‘s Pawns move down the board.
- Each move made by any player counts as a single move.
- Each piece’s possible moves are the same as in classical chess, with the following exceptions:
  - Pawns cannot move two squares forward.
  - The en passant move is not possible.
- Promotion:
  - Pawns promote to either a Bishop, Knight, or Rook when they reach the back row (promotion to a Queen is not allowed).
  - The players must perform promotions whenever possible. This means White must promote their Pawns when they reach any cell in the top row, and Black must promote their Pawns when they reach any cell in the bottom row.
Objective:
- The goal of the game is to capture the opponent’s Queen without losing your own.
- There will never be a draw or tie scenario like you might see in classical chess.

Given and the layout of pieces for games, implement a very basic engine for our simplified version of chess that determines 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 in moves; otherwise, print NO.

Input Format

The first line contains an integer, , denoting the number of games. The subsequent lines describe each game in the following format:

The first line contains three space-separated integers describing 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 chess piece in the form t c r, where is a character denoting the type of piece (where is Queen, is Knight, is Bishop, is Rook, and is a Pawn), and and denote the respective column and row on the board where the figure is located (where and ). These inputs are given as follows:
- Each of the first lines describes the type and location of a White piece.
- Each of the subsequent lines describes the type and location of a Black piece.

Constraints

Each player has exactly Queen, at most Pawns, at most Rooks, and at most minor pieces (i.e., a Bishop and/or Knight).
It is guaranteed that the initial location of each chess piece is distinct.
No pawn is initially placed in a row where it would promote.

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 instead.

Sample Input 0

1
2 1 1
Q B 1
P B 3
Q A 4

Sample Output 0

YES

Explanation 0

We play the following game of simplified chess:

White wins by moving their Pawn to and capturing Black‘s Queen, so we print YES on a new line.

Limbajul de programare folosit: cpp14

Cod:

#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;
}

Scor obtinut: 1.0

Submission ID: 464647889

Link challenge: https://www.hackerrank.com/challenges/simplified-chess-engine-ii/problem

Simplified Chess Engine II