#1083803 (C++17) No.2456 Stamp Art

• 問題: 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;
}