Recovering a Hole-Free Polyomino
National Olympiad — National round (2022 season)
Submission name: area.cpp
Problem summary
A connected hole-free square region is encoded by each inside square’s exposed-side count, with zeros outside. Recover area, perimeter and both right-angle corner counts.
Input
R S and the grid entries.
Output
Area, perimeter, convex/interior corners, concave/exterior corners, on four lines.
Constraints
1≤R,S≤500; entries0…4; valid connected hole-free encoding guaranteed.
Worked example
Input and output for the worked example discussed below.
Input
6 7 0 0 0 0 0 0 0 0 3 2 2 0 0 0 0 0 0 1 2 0 0 0 0 3 1 0 3 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0
Output
10 20 10 6
Solution analysis
- A zero may be exterior or a completely surrounded interior square. Add a zero border and flood-fill zeros connected to it, treating positive boundary cells as barriers. Hole-freeness makes unreached zeros interior.
- Area is the number of original cells not reached from outside. Perimeter is the sum of supplied exposed-side counts: each boundary segment belongs to one inside cell.
- Inspect the four cells around each vertex. One inside cell contributes a convex corner; three a concave corner. Two diagonal inside cells contribute two convex corners; two adjacent ones make a straight edge. The sample yields10,20,10,6.
Why it works
The positive boundary separates interior zeros from exterior zeros. Without holes, every exterior zero connects to the padded outside. Thus occupancy is recovered exactly; side sums count edges once, and local vertex patterns classify all right angles.
Watch out. Do not treat every zero as outside. Use four-neighbour flood fill and respect the source’s convex/interior versus concave/exterior terminology.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
// The positive boundary separates interior zeros from exterior zeros.
int main(){
int rows,cols;
cin>>rows>>cols;
vector<vector<int>>a(rows+2,vector<int>(cols+2,0));
int perimeter=0;
for(int r=1;r<=rows;r++){
for(int c=1;c<=cols;c++){
cin>>a[r][c];
perimeter+=a[r][c];
}
}
vector<vector<bool>>outside(rows+2,vector<bool>(cols+2,false));
queue<pair<int,int>>pending;
pending.push({0,0});
outside[0][0]=true;
int dr[4]={-1,1,0,0},dc[4]={0,0,-1,1};
while(!pending.empty()){
auto[r,c]=pending.front();
pending.pop();
for(int d=0;d<4;d++){
int nr=r+dr[d],nc=c+dc[d];
if(nr>=0&&nr<=rows+1&&nc>=0&&nc<=cols+1&&a[nr][nc]==0&&!outside[nr][nc]){
outside[nr][nc]=true;
pending.push({nr,nc});
}
}
}
vector<vector<int>>inside(rows+2,vector<int>(cols+2,0));
int area=0;
for(int r=1;r<=rows;r++){
for(int c=1;c<=cols;c++){
inside[r][c]=!outside[r][c];
area+=inside[r][c];
}
}
int convex=0,concave=0;
for(int r=0;r<=rows;r++){
for(int c=0;c<=cols;c++){
int x=inside[r][c],y=inside[r][c+1],z=inside[r+1][c],w=inside[r+1][c+1];
int count=x+y+z+w;
if(count==1){
convex++;
}
else if(count==3){
concave++;
}
else if(count==2&&x==w&&y==z){
convex+=2;
}
}
}
cout<<area<<'\n'<<perimeter<<'\n'<<convex<<'\n'<<concave<<'\n';
}