Dangerous Empty Seats
Национална олимпиада - Общински кръг 2026
Submission name: enemy.cpp
Problem summary
In each of two binary seating grids, count empty seats with at least three enemy-occupied side neighbours.
Input
Exactly two cases: rows columns followed by binary rows. 0 is empty and 1 is occupied.
Output
One count for each case.
Constraints
1 ≤ rows,columns ≤ 1000.
Worked example
The worked example illustrates the rule described in the analysis.
Input
2 2 11 10 1 1 0
Output
0 0
Solution analysis
- Inspect only cells containing 0. Occupied cells cannot be counted as dangerous empty seats.
- For each empty cell, check the four side neighbours with bounds checks. Count neighbours containing 1 and add one to the answer if the count is at least three.
- The two examples contain no empty cell with three occupied neighbours, giving zero for both. Diagonal enemies never contribute.
Why it works
Each empty cell is examined once and its four possible side neighbours are counted exactly. The threshold test therefore selects precisely the required cells.
Complexity: O(rows×columns) time and space for each case.
Watch out. Read exactly two grids, not a leading test count. Do not count diagonals or treat cells outside the grid as enemies.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each empty cell is examined once and its four possible side neighbours are counted
// exactly. The threshold test therefore selects precisely the required cells.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
for(int test=0;test<2;++test){
int rows,columns;
cin>>rows>>columns;
vector<string>grid(rows);
for(string&row:grid){
cin>>row;
}
const int dr[]={-1,1,0,0};
const int dc[]={0,0,-1,1};
int answer=0;
for(int r=0;r<rows;++r){
for(int c=0;c<columns;++c){
if(grid[r][c]!='0'){
continue;
}
int enemies=0;
for(int direction=0;direction<4;++direction){
int nr=r+dr[direction];
int nc=c+dc[direction];
if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]=='1'){
++enemies;
}
}
answer+=enemies>=3;
}
}
cout<<answer<<'\n';
}
}