/* This program checks which player has check, whether it is a check or checkmate and finds all possible moves for the player who has check. Input: On the first line input p: number of pieces on chessboard. p lines follow, each in the form tcr t represents the type of the chesspiece - this character is from the set {KQRBHPkqrbhp}, representing in this order the king, queen, rook, bishop, knight (horse), and pawn. The pieces belonging to the White player are marked by lowercase characters; the upper side of the chessboard (lower row numbers) belongs to him, hence white pawns move in the positive r direction. The pieces belonging to the Black player are marked by uppercase characters; the lower side of the chessboard (greater row numbers) belongs to him, hence black pawns move in the negative r direction. c is a lowercase letter representing the column, where this piece is; first column is 'a' r is a number representing the row, where this piece is; first row is 1, last is N Examples: 4 ke1 Hd3 hd5 Ke7 4 he2 kc3 Hf4 Kd5 6 ka1 Hd1 Hd2 Hb3 Hc3 Kg6 7 ka1 Hd1 Hd2 Hb3 Hc3 Kg6 rb7 9 Ka1 Rg1 rh1 Ra2 hc2 rh2 ra5 rb5 kf6 6 ka1 Rh2 Bd4 Rb5 Kg6 qc7 9 Pc2 Pd2 Pe2 Pc3 kd3 Pe3 Pd4 pe4 Kd5 You can change N below to change the chessboard size */ int n=8; #include #include #include #include using namespace std; struct Point{ int r; int c; Point(int a, int b) : r(a), c(b) {} }; struct Piece{ bool color; // white - true, black - false mutable bool canMove; char type; int r; int c; bool movesOrt() const {return type=='Q' || type=='R';} bool movesDiag() const {return type=='Q' || type=='B';} Piece(int rr, int cc) : r(rr), c(cc), canMove(true){} const bool operator==(const Piece &o) const { return r==o.r && c==o.c; } bool moves(bool dir) const{return dir ? movesDiag() : movesOrt();} }; struct colcomp { bool operator() (const Piece* p1, const Piece* p2) const { return p1->c < p2->c; } }; struct rowcomp { bool operator() (const Piece* p1, const Piece* p2) const { return p1->r < p2->r; } }; int sgn(int x){ return x<0 ? -1 : (x==0 ? 0 : 1); } vector> rowSets; vector> colSets; vector> sumSets; vector> difSets; int HORSE_DR [8]={2, 1, -1, -2, -2, -1, 1, 2}; int HORSE_DC [8]={1, 2, 2, 1, -1, -2, -2, -1}; int KING_DR [8]={-1, -1, 0, 1, 1, 1, 0, -1}; int KING_DC [8]={ 0, 1, 1, 1, 0, -1, -1, -1}; template void findThreat(set &Set, Piece *piece, bool color, int &result, const Piece* &bad, bool direction, bool mov, bool setCanMove, bool output){ auto it=Set.lower_bound(piece); if (it!=Set.begin()){ it--; const Piece *p=(*it); if (p->color!=color){ if (p->moves(direction) && (!mov || p->canMove)){ if (output) cout << "Move " << (char)(p->type - (color ? 0 : 'p'-'P')) << " to " << (char)('a'+piece->c) << (piece->r+1) << "\n"; result++; bad=p; } } else if (setCanMove && it!=Set.begin()){ it--; const Piece *p2=(*it); if (p2->color!=color && p2->moves(direction)) p->canMove=false; } } it=Set.upper_bound(piece); if (it!=Set.end()){ const Piece *p=(*it); if (p->color!=color){ if (p->moves(direction) && (!mov || p->canMove)){ if (output) cout << "Move " << (char)(p->type + (color ? 0 : 'p'-'P')) << " to " << (char)('a'+piece->c) << (piece->r+1) << "\n"; result++; bad=p; } } else if (setCanMove && ++it!=Set.end()){ const Piece *p2=(*it); if (p2->color!=color && p2->moves(direction)) p->canMove=false; } } } //checks whether a piece at [r, c] of color color is threatened pair isThreatened(int r, int c, bool color, bool exists, bool mov, bool setCanMove, bool output){ const Piece *bad=NULL; int result=0; for (int i=0; i<8; i++){ int r2=r+HORSE_DR[i]; int c2=c+HORSE_DC[i]; if (r2<0 || r2>=n) continue; auto it=rowSets[r2].find(new Piece(r2, c2)); if (it==rowSets[r2].end()) continue; const Piece *p=(*it); if (p->type=='H' && p->color!=color && (!mov || p->canMove)){ if (output) cout << "Move " << (color ? "H" : "h") << " to " << (char)('a'+c) << r << "\n"; result++; bad=p; } } for (int i=0; i<8; i++){ int r2=r+KING_DR[i]; int c2=c+KING_DC[i]; if (r2<0 || r2>=n) continue; auto it=rowSets[r2].find(new Piece(r2, c2)); if (it==rowSets[r2].end()) continue; const Piece *p=(*it); if (p->type=='K' && p->color!=color && (!mov || p->canMove)){ if (output) cout << "Move " << (color ? "K" : "k") << " to " << (char)('a'+c) << r << "\n"; result++; bad=p; } } int r2 = color ? r+1 : r-1; if (exists){ int c2=c-1; if (r2>=0 && r2type=='P' && p->color!=color && (!mov || p->canMove)){ if (output) cout << "Move " << (color ? "P" : "p") << " to " << (char)('a'+c) << r << "\n"; result++; bad=p; } } c2+=2; auto it2=rowSets[r2].find(new Piece(r2, c2)); if (it2!=rowSets[r2].end()){ const Piece *p=(*it2); if (p->type=='P' && p->color!=color && (!mov || p->canMove)){ if (output) cout << "Move " << (color ? "P" : "p") << " to " << (char)('a'+c) << r << "\n"; result++; bad=p; } } } } else{ int c2=c; if (r2>=0 && r2type=='P' && p->color!=color && (!mov || p->canMove)){ if (output) cout << "Move " << (color ? "P" : "p") << " to " << (char)('a'+c) << r << "\n"; result++; bad=p; } } } } findThreat(rowSets[r], new Piece(r, c), color, result, bad, false, mov, setCanMove, output); findThreat(colSets[c], new Piece(r, c), color, result, bad, false, mov, setCanMove, output); findThreat(sumSets[r+c], new Piece(r, c), color, result, bad, true, mov, setCanMove, output); findThreat(difSets[r-c+n], new Piece(r, c), color, result, bad, true, mov, setCanMove, output); return make_pair(result, bad); } int main(){ int f; cin >> f; rowSets=vector>(n); colSets=vector>(n); sumSets=vector>(2*n); difSets=vector>(2*n); Point kingb(-1, -1); Point kingw(-1, -1); int r, c; char _c; char type; for (int i=0; i> type >> _c >> r; --r; c=_c-'a'; Piece* p = new Piece(r, c); if (type=='k') kingw=Point(r, c); if (type=='K') kingb=Point(r, c); p->color = type>='a'; if (type>='a'){ type-= 'a'-'A'; } p->type = type; rowSets[r].insert(p); colSets[c].insert(p); sumSets[r+c].insert(p); difSets[r-c+n].insert(p); } pair threatb=isThreatened(kingb.r, kingb.c, false, true, false, true, false); pair threatw=isThreatened(kingw.r, kingw.c, true, true, false, true, false); if (threatb.first && threatw.first) cout << "Impossible, both kings under threat\n"; else if (threatw.first==0 && threatb.first==0) cout << "Safe, no king under threat\n"; else{ pair threat = threatb.first ? threatb : threatw; bool color = threatb.first==0; r = threatb.first ? kingb.r : kingw.r; c = threatb.first ? kingb.c : kingw.c; rowSets[r].erase(new Piece(r, c)); colSets[c].erase(new Piece(r, c)); sumSets[r+c].erase(new Piece(r, c)); difSets[r-c+n].erase(new Piece(r, c)); int moves=0; for (int i=0; i<8; i++){ int r2=r+KING_DR[i]; int c2=c+KING_DC[i]; if (r2<0 || c2<0 || r2>=n || c2>=n) continue; Piece *p = new Piece(r2, c2); p->type='K'; auto it=rowSets[r2].find(p); if (it!=rowSets[r2].end()){ Piece* kicked = *it; if (kicked->color==color) continue; rowSets[r2].erase(kicked); colSets[c2].erase(kicked); sumSets[r2+c2].erase(kicked); difSets[r2-c2+n].erase(kicked); rowSets[r2].insert(p); colSets[c2].insert(p); sumSets[r2+c2].insert(p); difSets[r2-c2+n].insert(p); if (isThreatened(r2, c2, color, true, false, false, false).first==false){ moves++; cout << "Move " << (color ? "k" : "K") << " to " << (char)('a'+c2) << (r2+1) << "\n"; } rowSets[r2].erase(p); colSets[c2].erase(p); sumSets[r2+c2].erase(p); difSets[r2-c2+n].erase(p); rowSets[r2].insert(kicked); colSets[c2].insert(kicked); sumSets[r2+c2].insert(kicked); difSets[r2-c2+n].insert(kicked); } else{ rowSets[r2].insert(p); colSets[c2].insert(p); sumSets[r2+c2].insert(p); difSets[r2-c2+n].insert(p); if (isThreatened(r2, c2, color, true, false, false, false).first==false){ moves++; cout << "Move " << (color ? "k" : "K") << " to " << (char)('a'+c2) << (r2+1) << "\n"; } rowSets[r2].erase(p); colSets[c2].erase(p); sumSets[r2+c2].erase(p); difSets[r2-c2+n].erase(p); } } Piece *p = new Piece(r, c); p->type='K'; p->canMove=false; rowSets[r].insert(p); colSets[c].insert(p); sumSets[r+c].insert(p); difSets[r-c+n].insert(p); if (threat.first==1){ //if there is only 1 piece threatening the king, we may put something into its way const Piece* bad = threat.second; pair kick = isThreatened(bad->r, bad->c, !color, true, true, false, true); if (kick.first) moves+=kick.first; int br = bad->r; int bc = bad->c; if (bad->movesOrt() || bad->movesDiag()){ br-=sgn(br-r); bc-=sgn(bc-c); while (br!=r || bc!=c){ pair kick = isThreatened(br, bc, !color, false, true, false, true); if (kick.first) moves+=kick.first; br-=sgn(br-r); bc-=sgn(bc-c); } } } cout << (color ? "White " : "Black "); if (moves) cout << "Check - " << moves << " Plausible Moves\n"; else cout << "Checkmate\n"; } return 0; }

Challenge: Chess Engine