Possible Placements of the Last Battleship
National Olympiad — National round (2013 season)
Submission name: battle.cpp
Problem summary
Count possible horizontal and vertical positions of one remaining 1×K ship. It may not overlap or touch any destroyed ship cell, including at a corner.
Source clarification. The output paragraph says maximum number of ships, but the question and official examples count alternative placements of the single remaining ship, separately by orientation.
Input
M N; K; then M rows of N binary values indicating destroyed cells.
Output
Horizontal and vertical alternative placement counts.
Constraints
1 ≤ M,N ≤ 1000; 1 ≤ K ≤ max(M,N).
Worked example
Input and output for the worked example discussed below.
Input
5 6 2 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
Output
8 7
Solution analysis
- Mark every destroyed cell and its eight neighbours forbidden. A new ship is legal exactly when each of its cells avoids this grid, enforcing both side and diagonal separation.
- Scan each row with a free-run counter. Once a run reaches K, every additional allowed cell completes one new horizontal window. Repeat down columns for vertical alternatives.
- A free run of length 5 contains 4 alternatives for a length-2 ship, not 2, because these placements need not coexist. In the sample the row and column windows total 8 and 7.
Why it works
The forbidden cells encode exactly all forbidden contacts. Every legal placement is a length-K free window, counted exactly once at its last cell. Separate row and column scans therefore count both orientations correctly.
Watch out. Count alternative positions of one ship, not simultaneous packing. For K=1 both reported counts are equal. Exclude diagonal contact.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows;
int columns;
int length;
cin>>rows>>columns>>length;
vector<vector<bool>>blocked(rows+2,vector<bool>(columns+2));
for(int r=1;r<=rows;r++){
for(int c=1;c<=columns;c++){
int occupied;
cin>>occupied;
if(occupied){
for(int x=r-1;x<=r+1;x++){
for(int y=c-1;y<=c+1;y++){
blocked[x][y]=true;
}
}
}
}
}
int horizontal=0;
int vertical=0;
for(int r=1;r<=rows;r++){
int run=0;
for(int c=1;c<=columns;c++){
run=blocked[r][c]?0:run+1;
// Each ending cell identifies one alternative free window.
if(run>=length){
horizontal++;
}
}
}
for(int c=1;c<=columns;c++){
int run=0;
for(int r=1;r<=rows;r++){
run=blocked[r][c]?0:run+1;
if(run>=length){
vertical++;
}
}
}
cout<<horizontal<<' '<<vertical<<'\n';
}