Fill the Star Rectangle
National Olympiad — Regional round (2015 season)
Submission name: grid.cpp
Problem summary
Replace as few dots as possible by stars so that all stars form one filled axis-aligned rectangle. At least one star is initially present. Print the resulting grid.
Input
H W followed by H rows of W characters, each a star or dot.
Output
The changed grid without spaces between characters.
Constraints
2 ≤ H, W ≤ 50; at least one initial star.
Worked example
An independently prepared example for this explanation.
Input
2 3 *.. .*.
Output
**. **.
Solution analysis
- Any rectangle containing all existing stars must extend from at least the smallest occupied row to the largest, and likewise for columns. These four extremes determine the bounding rectangle.
- Scan the grid once to find the extremes, then fill every position inside that rectangle with a star. Positions outside it stay unchanged.
- In the example the stars occupy rows 0–1 and columns 0–1. Filling that 2-by-2 rectangle changes two dots; column 2 stays dotted.
Why it works
Every feasible filled rectangle must contain the bounding rectangle, because it must contain each extreme star. Therefore every dot inside the bounding rectangle must be changed in any solution. Filling exactly those dots forms a feasible rectangle and makes the minimum number of changes.
Watch out. Find all four extremes. Do not fill the entire rows or columns outside the bounding rectangle.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w;
cin >> h >> w;
vector<string> grid(h);
int top = h;
int bottom = -1;
int left = w;
int right = -1;
for (int r = 0; r < h; ++r) {
cin >> grid[r];
for (int c = 0; c < w; ++c) {
if (grid[r][c] == '*') {
top = min(top, r);
bottom = max(bottom, r);
left = min(left, c);
right = max(right, c);
}
}
}
// Every feasible rectangle must include this entire bounding box.
for (int r = top; r <= bottom; ++r) {
for (int c = left; c <= right; ++c) {
grid[r][c] = '*';
}
}
for (const string &row : grid) {
cout << row << '\n';
}
return 0;
}