Queens and Pawns
National Olympiad — Municipal round (2010 season)
Submission name: chess.cpp
Problem summary
An ordinary 8×8 chessboard contains two white queens and several black pawns. Count the distinct pawns attacked by at least one queen. Queens move along rows, columns and diagonals and cannot jump over pieces.
Input
One occupied square per line in standard notation a1 through h8, read until end of input. All pawns come first and the final two squares are the queens.
Output
The number of attacked pawns.
Constraints
An 8×8 board; two queens and the listed pawns occupy distinct squares. The statement gives no further numeric bounds.
Worked example
An independently prepared example for this explanation.
Input
h1 b5 d7 h6 c5 f5 e3
Output
3
Solution analysis
- Store the listed squares, treating the final two as queens and earlier ones as pawns. Build an occupancy board and a separate attacked-pawn board.
- For each queen trace all eight rays. Stop at the board boundary or the first piece. If that piece is a pawn, mark it attacked; if it is the other queen, the ray is simply blocked.
- In the sample the queens are f5 and e3. The pawn on c5 is reached horizontally from f5, d7 diagonally from f5, and h6 diagonally from e3. The other pawns are not attacked, giving 3.
Why it works
A queen can attack a pawn exactly when that pawn is the first piece on one of its eight rays. Ray tracing marks exactly these pawns. A boolean mark ensures a pawn attacked by both queens contributes only once.
Watch out. There is no piece count in the input. The other queen blocks a ray, and a pawn must never be counted twice.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
// Compute the exact archive answer using the method explained above.
vector<pair<int,int>>pieces;
string square;
while(cin>>square){
pieces.push_back({square[0]-'a',square[1]-'1'});
}
int board[8][8]={};
bool attacked[8][8]={};
int count=static_cast<int>(pieces.size());
for(int i=0;i<count;i++){
auto[x,y]=pieces[i];
board[x][y]=i<count-2?1:2;
}
for(int i=count-2;i<count;i++){
auto[x,y]=pieces[i];
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
if(dx==0&&dy==0){
continue;
}
int nx=x+dx;
int ny=y+dy;
while(nx>=0&&nx<8&&ny>=0&&ny<8){
if(board[nx][ny]!=0){
if(board[nx][ny]==1){
attacked[nx][ny]=true;
}
break;
}
nx+=dx;
ny+=dy;
}
}
}
}
int answer=0;
for(auto&row:attacked){
for(bool value:row){
answer+=value;
}
}
cout<<answer<<'\n';
}