結果
| 問題 | No.2456 Stamp Art |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 329 ms / 5,000 ms |
| コード長 | 7,320 bytes |
| コンパイル時間 | 1,143 ms |
| コンパイル使用メモリ | 83,344 KB |
| 実行使用メモリ | 38,912 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:10 |
| 合計ジャッジ時間 | 6,798 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <vector> // Ensure vector header is included
using namespace std;
int H, W; // Grid dimensions
vector<string> S; // Input grid representation
vector<vector<int>> P; // 2D prefix sums array for counting white cells '.'
vector<vector<int>> diff; // 2D difference array for efficiently computing coverage counts
/**
* @brief Calculates the number of white cells ('.') within a given rectangular region.
* Uses the precomputed 2D prefix sum array P.
* Assumes 1-based indexing for coordinates (r1, c1) to (r2, c2).
* Assumes the coordinates define a valid rectangle within grid bounds [1, H] x [1, W],
* based on how this function is called within the check function.
*
* @param r1 Top row index (1-based)
* @param c1 Left column index (1-based)
* @param r2 Bottom row index (1-based)
* @param c3 Right column index (1-based)
* @return The count of white cells within the specified rectangle.
*/
int count_white_simplified(int r1, int c1, int r2, int c2) {
// Standard 2D prefix sum query formula
return P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1];
}
/**
* @brief Checks if the grid X can be generated using a stamp of size k x k.
* This is true if and only if every black cell ('#') in X is covered by at least one
* k x k square region that consists entirely of black cells in X.
*
* @param k The stamp size to check.
* @return True if grid X can be generated with a k x k stamp, False otherwise.
*/
bool check(int k) {
// k must be a positive integer. Stamp size k=0 is invalid.
if (k <= 0) return false;
// Reset the difference array for the current check.
// Initialize all elements to 0. Looping through rows and using fill is one way.
for (int i = 0; i <= H + 1; ++i) {
fill(diff[i].begin(), diff[i].end(), 0);
}
// Step 1: Identify all k x k squares that are entirely black ('#') in the input grid S.
// For each such square, update the difference array to mark its contribution to cell coverage.
// Iterate through all possible top-left corners (i, j) for a k x k square.
for (int i = 1; i <= H - k + 1; ++i) {
for (int j = 1; j <= W - k + 1; ++j) {
// Check if the k x k square starting at (i, j) contains any white cells.
// The square covers cell range [i, i+k-1] x [j, j+k-1].
if (count_white_simplified(i, j, i + k - 1, j + k - 1) == 0) {
// If the square is all black (0 white cells):
// Apply updates to the difference array. This technique allows us to later
// compute the total number of covering squares for each cell efficiently.
// Increment count at the top-left corner (i, j).
diff[i][j]++;
// Decrement counts at boundaries to confine the +1 effect within the k x k square.
// Indices i+k and j+k can reach H+1 and W+1, hence the diff array size H+2, W+2.
diff[i + k][j]--;
diff[i][j + k]--;
// Add back the count at (i+k, j+k) because it was subtracted twice
// (once for row boundary i+k, once for column boundary j+k).
diff[i + k][j + k]++;
}
}
}
// Step 2: Compute 2D prefix sums on the difference array.
// This transforms the difference array into an array where diff[i][j] stores the
// total count of all-black k x k squares covering the cell (i, j).
// Pass 1: Compute cumulative sums down columns. Propagates effects vertically.
for (int i = 1; i <= H + 1; ++i) { // Loop includes boundary index H+1.
for (int j = 1; j <= W + 1; ++j) { // Loop includes boundary index W+1.
diff[i][j] += diff[i - 1][j];
}
}
// Pass 2: Compute cumulative sums across rows. Propagates effects horizontally.
for (int i = 1; i <= H + 1; ++i) { // Loop includes boundary index H+1.
for (int j = 1; j <= W + 1; ++j) { // Loop includes boundary index W+1.
diff[i][j] += diff[i][j - 1];
}
}
// Step 3: Verify the generation condition.
// Check if every black cell ('#') in the original grid X (represented by S)
// has a coverage count greater than 0.
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
// Access S using 0-based indexing (S[i-1][j-1]) corresponding to 1-based grid cell (i, j).
if (S[i - 1][j - 1] == '#') {
// If the cell is black, check its coverage count computed in Step 2.
if (diff[i][j] == 0) {
// If the count is 0, this black cell is not covered by any all-black k x k square.
// Thus, the grid cannot be generated with stamp size k.
return false;
}
}
}
}
// If the loop completes without returning false, it means all black cells are covered.
// The grid can be generated with stamp size k.
return true;
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read grid dimensions H and W
cin >> H >> W;
// Resize grid representation S
S.resize(H);
// Initialize prefix sum array P with size (H+1) x (W+1), using 1-based indexing. All values initially 0.
P.assign(H + 1, vector<int>(W + 1, 0));
// Initialize difference array diff with size (H+2) x (W+2) to safely handle boundary updates. All values initially 0.
diff.assign(H + 2, vector<int>(W + 2, 0));
// Read the grid configuration from input
for (int i = 0; i < H; ++i) {
cin >> S[i];
}
// Precompute the 2D prefix sums for white cells ('.')
// P[i][j] will store the count of '.' in the rectangle from (1,1) to (i,j).
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
// Update P[i][j] using the standard 2D prefix sum formula.
// Check cell S[i-1][j-1] which corresponds to grid cell (i, j).
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + (S[i - 1][j - 1] == '.');
}
}
// Perform binary search to find the maximum possible stamp size k.
// The property that if size k works, any size k' < k also works, allows binary search.
int low = 1; // The minimum possible stamp size is 1 (guaranteed possible by problem constraints).
int high = min(H, W); // The maximum possible stamp size is limited by grid dimensions.
int ans = 0; // Stores the maximum valid k found so far. Initialized to 0.
while (low <= high) {
int mid = low + (high - low) / 2; // Calculate midpoint candidate size. Avoids potential overflow vs (low+high)/2.
if (check(mid)) { // Check if the current candidate size 'mid' works.
ans = mid; // If 'mid' works, it's a possible answer. Store it.
low = mid + 1; // Try to find a larger working size.
} else {
high = mid - 1; // If 'mid' doesn't work, the maximum size must be smaller.
}
}
// Output the largest k found that satisfies the condition.
cout << ans << endl;
return 0;
}