This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1137
Adhoc.
How I did it
- Read the chess board configuration and save the black and white king row and col in global variables.
- First, I check if the black king is under attack and print the black king is under attack. Otherwise I check if the white king is under attack and print the white king is under attack, otherwise print no king is under attack.
Hints
- The input is really small, so a complete search approach is enough. (My algorithm 0.16 sec).
- The queen has the same movement as bishop and rock.
- A king is under attack of a bishop if: abs(kingRow – otherPieceRow) – abs(kingCol – otherPieceCol) == 0.
Code
#include <iostream> #include <cstdio> #include <cctype> #include <cstdlib> using namespace std; int rowBlack, colBlack, rowWhite, colWhite; char chessBoard[9][9]; bool readGame() { string tmp, myStr = ""; int index = 0; for(int a=0; a<8; a++) { cin>>tmp; myStr += tmp; } bool flag = false; for(int x=0; x<8; x++) for(int y=0; y<8; y++, index++) { chessBoard[x][y] = myStr[index]; if(myStr[index] != '.') flag = true; if(chessBoard[x][y] == 'k') { rowBlack = x; colBlack = y; } if(chessBoard[x][y] == 'K') { rowWhite = x; colWhite = y; } } return flag; } bool checkRock(int a,int b, int kRow, int kCol, char king) { if(a != kRow && b != kCol) return false; for(int x=a+1; x<8; x++) { if(chessBoard[x][b] == king) return true; else if(isalpha(chessBoard[x][b]) && chessBoard[x][b] != king) break; } for(int x=a-1; x>=0; x--) { if(chessBoard[x][b] == king) return true; else if(isalpha(chessBoard[x][b]) && chessBoard[x][b] != king) break; } for(int x=b+1; x<8; x++) { if(chessBoard[a][x] == king) return true; else if(isalpha(chessBoard[a][x]) && chessBoard[a][x] != king) break; } for(int x=b-1; x>=0; x--) { if(chessBoard[a][x] == king) return true; else if(isalpha(chessBoard[a][x]) && chessBoard[a][x] != king) break; } return false; } bool checkBishop(int x, int y, int rBlack, int cBlack, char king) { if(abs(x - rBlack) - abs(y - cBlack) != 0) return false; for(int a=x-1, b=y-1; a>=0 && b>=0; a--, b--) { if(chessBoard[a][b] == king) return true; else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king) break; } for(int a=x-1, b=y+1; a>=0 && b<8; a--, b++) { if(chessBoard[a][b] == king) return true; else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king) break; } for(int a=x+1, b=y-1; a<8 && b>=0; a++, b--) { if(chessBoard[a][b] == king) return true; else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king) break; } for(int a=x+1, b=y+1; a<8 && b<8; a++, b++) { if(chessBoard[a][b] == king) return true; else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king) break; } return false; } bool checkKnight(int x, int y, int rBlack, int cBlack, char king) { if(x-2>=0 && y-1>=0 && chessBoard[x-2][y-1] == king) return true; else if(x-1>=0 && y-2>=0 && chessBoard[x-1][y-2] == king) return true; else if(x+1<8 && y-2>=0 && chessBoard[x+1][y-2] == king) return true; else if(x+2<8 && y-1>=0 && chessBoard[x+2][y-1] == king) return true; else if(x+2<8 && y+1<8 && chessBoard[x+2][y+1] == king) return true; else if(x+1<8 && y+2<8 && chessBoard[x+1][y+2] == king) return true; else if(x-1>=0 && y+2<8 && chessBoard[x-1][y+2] == king) return true; else if(x-2>=0 && y+1<8 && chessBoard[x-2][y+1] == king) return true; else return false; } bool checkPawn(int x,int y, int rowBlack, int colBlack, char king) { if(x-1 >=0 && y-1 >=0 && chessBoard[x-1][y-1] == king) return true; else if(x-1 >=0 && y+1<8 && chessBoard[x-1][y+1] == king) return true; else return false; } bool checkPawnWhite(int x,int y, int rowBlack, int colBlack, char king) { if(x+1<8 && y-1 >=0 && chessBoard[x+1][y-1] == king) return true; else if(x+1<8 && y+1<8 && chessBoard[x+1][y+1] == king) return true; else return false; } bool checkBlack() { for(int x=0; x<8; x++) for(int y=0; y<8; y++) { if(chessBoard[x][y] != '.' && isupper(chessBoard[x][y])) { if(chessBoard[x][y] == 'R') { if(checkRock(x,y, rowBlack, colBlack, 'k')) return true; } else if(chessBoard[x][y] == 'B') { if(checkBishop(x,y, rowBlack, colBlack, 'k')) return true; } else if(chessBoard[x][y] == 'Q') { if(checkRock(x,y, rowBlack, colBlack, 'k') || checkBishop(x,y, rowBlack, colBlack, 'k')) return true; } else if(chessBoard[x][y] == 'N') { if(checkKnight(x, y, rowBlack, colBlack, 'k')) return true; } else if(chessBoard[x][y] == 'P') { if(checkPawn(x,y, rowBlack, colBlack, 'k')) return true; } } } return false; } bool checkWhite() { for(int x=0; x<8; x++) for(int y=0; y<8; y++) { if(chessBoard[x][y] != '.' && islower(chessBoard[x][y])) { if(chessBoard[x][y] == 'r') { if(checkRock(x,y, rowWhite, colWhite, 'K')) return true; } else if(chessBoard[x][y] == 'b') { if(checkBishop(x,y, rowWhite, colWhite, 'K')) return true; } else if(chessBoard[x][y] == 'q') { if(checkRock(x,y, rowWhite, colWhite, 'K') || checkBishop(x,y, rowWhite, colWhite, 'K')) return true; } else if(chessBoard[x][y] == 'n') { if(checkKnight(x, y, rowWhite, colWhite, 'K')) return true; } else if(chessBoard[x][y] == 'p') { if(checkPawnWhite(x,y, rowWhite, colWhite, 'K')) return true; } } } return false; }int main() { int casos = 1; while(readGame()) { if(checkBlack()) printf("Game #%d: black king is in check.\n", casos++); else if(checkWhite()) printf("Game #%d: white king is in check.\n", casos++); else printf("Game #%d: no king is in check.\n", casos++); } return 0; }