#1083736 (C++17) No.179 塗り分け

• 問題: No.179 塗り分け
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:58:33
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 253 ms / 3,000 ms
• コード長: 7,817 bytes
• コンパイル時間: 1,724 ms
• コンパイル使用メモリ: 107,472 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 12:59:48
• 合計ジャッジ時間: 2,934 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 6
other	AC * 40

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set> // Using unordered_set for potentially better average time performance
#include <queue>
#include <utility> // For std::pair
#include <functional> // For std::hash

// Define a hash function structure for std::pair<int, int>.
// This is required to use std::pair<int, int> as keys in std::unordered_set.
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        // Use std::hash to get hash values for the first and second elements of the pair.
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        
        // Combine the hash values. A simple and common technique is to use XOR combined with a bit shift.
        // This helps in distributing hash values better and reducing collisions compared to plain XOR.
        return h1 ^ (h2 << 1); 
    }
};

using namespace std;

int H, W; // Grid dimensions: Height H, Width W
vector<string> S; // Vector of strings to store the grid configuration
// Use an unordered_set to store the coordinates of black cells ('#').
// This allows for efficient average time complexity O(1) checks for cell existence.
unordered_set<pair<int, int>, pair_hash> black_cells;

// Function to check if a given translation vector (dr, dc) allows for a valid partitioning
// of the black cells into two sets, Red (R) and Blue (B'), such that R = B' + (dr, dc).
// A partitioning is valid if:
// 1. R and B' are non-empty.
// 2. R union B' = set of all black cells.
// 3. R intersection B' is empty.
// 4. R is obtained by translating B' by vector (dr, dc).
bool check(int dr, int dc) {
    // `visited` set keeps track of black cells that have already been assigned to a connected component
    // during the Breadth-First Search (BFS) traversal.
    unordered_set<pair<int, int>, pair_hash> visited;
    
    // Iterate over all black cells. Each cell potentially starts a BFS for a new connected component.
    for (const auto& p : black_cells) {
        // If this cell `p` has already been visited (i.e., it's part of a component already processed), skip it.
        if (visited.count(p)) {
            continue;
        }

        // Start a BFS from cell `p` to find its connected component.
        // Two black cells p1 and p2 are considered connected if p2 = p1 + (dr, dc) or p1 = p2 + (dr, dc).
        int component_size = 0; // Counter for the number of cells in the current component.
        queue<pair<int, int>> q; // Queue for the BFS traversal.

        q.push(p); // Start BFS from p.
        visited.insert(p); // Mark p as visited.
        
        // Process cells in the queue until it's empty.
        while (!q.empty()) {
            pair<int, int> curr = q.front(); // Get the current cell from the front of the queue.
            q.pop(); // Remove the current cell from the queue.
            component_size++; // Increment the component size.

            int r = curr.first; // Row coordinate of the current cell.
            int c = curr.second; // Column coordinate of the current cell.

            // Check potential neighbor in the direction of translation: p + (dr, dc)
            pair<int, int> next1 = {r + dr, c + dc};
            // Check if this potential neighbor is a black cell.
            // `black_cells.count()` implicitly checks if coordinates are within grid bounds,
            // because `black_cells` only contains valid coordinates of black cells within the grid.
            if (black_cells.count(next1)) {
                 // If it's a black cell and hasn't been visited yet:
                 if (visited.find(next1) == visited.end()) { 
                    visited.insert(next1); // Mark it as visited.
                    q.push(next1); // Add it to the queue to process later.
                }
            }

            // Check potential neighbor in the opposite direction of translation: p - (dr, dc)
            pair<int, int> next2 = {r - dr, c - dc};
            // Check if this potential neighbor is a black cell.
            if (black_cells.count(next2)) {
                 // If it's a black cell and hasn't been visited yet:
                 if (visited.find(next2) == visited.end()) {
                    visited.insert(next2); // Mark it as visited.
                    q.push(next2); // Add it to the queue to process later.
                }
            }
        }

        // A key derived condition: For a valid partitioning using vector (dr, dc),
        // every connected component in the graph formed by the translation relation
        // must contain an even number of cells.
        if (component_size % 2 != 0) {
            // If any component has an odd size, this translation vector (dr, dc) cannot work.
            return false; 
        }
    }
    
    // If the loop finishes without returning false, it means all connected components have even size.
    // The condition that Red and Blue sets must be non-empty is implicitly satisfied.
    // This is because the initial check in `main` ensures |B| >= 2 and is even.
    // An even-sized component must have at least 2 cells. Partitioning it gives at least 1 cell to R and 1 cell to B'.
    // As long as there's at least one component (which is true for |B| >= 2), both R and B' will be non-empty.
    return true; // This translation vector (dr, dc) allows a valid partitioning.
}


int main() {
    // Use fast I/O operations to speed up input reading.
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    // Read grid dimensions H (height/rows) and W (width/columns).
    cin >> H >> W;
    // Resize the vector of strings to hold H rows.
    S.resize(H);
    // Read the grid configuration row by row.
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
        // Identify black cells ('#') and store their coordinates (0-indexed).
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') {
                // Using {row, column} pair for coordinates.
                black_cells.insert({i, j});
            }
        }
    }

    // Perform initial checks based on the total number of black cells |B|.
    // If there are no black cells (|B| = 0), we cannot form non-empty Red and Blue sets. Output NO.
    // If the total number of black cells is odd, it's impossible to partition them into two sets of equal size. Output NO.
    if (black_cells.size() == 0 || black_cells.size() % 2 != 0) {
        cout << "NO" << endl;
        return 0;
    }
    // If the code reaches here, it means |B| >= 2 and is even. This guarantees that if a valid partitioning exists, R and B' will be non-empty.

    // Iterate through all possible non-zero translation vectors (dr, dc).
    // The range for dr is [-(H-1), H-1] and for dc is [-(W-1), W-1].
    // This range covers all possible relative displacements between any two cells within the grid.
    for (int dr = -(H - 1); dr < H; ++dr) {
        for (int dc = -(W - 1); dc < W; ++dc) {
             // The translation vector (0, 0) is explicitly disallowed.
             // If (dr, dc) = (0, 0), then R = B', violating the requirement that R and B' must be disjoint
             // unless B is empty (which is handled earlier).
             if (dr == 0 && dc == 0) continue; 
            
            // Check if the current translation vector (dr, dc) allows a valid partitioning.
            if (check(dr, dc)) {
                // If a valid translation vector is found, output YES and terminate the program.
                cout << "YES" << endl;
                return 0;
            }
        }
    }

    // If the loops complete without finding any valid translation vector, it means no such partitioning is possible. Output NO.
    cout << "NO" << endl;
    return 0;
}