#1083986 (C++17) No.1949 足し算するだけのパズルゲーム(2)

• 問題: No.1949 足し算するだけのパズルゲーム(2)
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:13:16
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 92 ms / 3,000 ms
• コード長: 6,786 bytes
• コンパイル時間: 1,235 ms
• コンパイル使用メモリ: 108,032 KB
• 実行使用メモリ: 10,388 KB
• 最終ジャッジ日時: 2025-05-14 13:14:04
• 合計ジャッジ時間: 3,523 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
other	AC * 26

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // For std::pair
#include <functional> // For std::greater

using namespace std;

// Use long long for attack power as it can grow very large, potentially exceeding
// the capacity of a 32-bit integer. Summing up many large attack values requires 64-bit.
typedef long long ll;

// Define a type alias for the elements stored in the priority queue for clarity.
// Each element stores {attack_power, {row, col}} of an enemy cell.
using PQElement = pair<ll, pair<int, int>>;

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

    int H, W, Y, X; // Grid dimensions HxW, starting coordinates Y,X
    cin >> H >> W >> Y >> X;

    // Adjust input coordinates from 1-based to 0-based indexing for array access
    Y--; 
    X--;

    // Store grid attack values. Use long long for potentially large values.
    vector<vector<ll>> A(H, vector<ll>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
        }
    }

    // Initialize player's power with the value at the starting cell
    ll current_power = A[Y][X];
    
    // Calculate the total number of enemies to defeat
    int total_enemies = H * W - 1;

    // Handle the edge case where the grid has only one cell (H=1, W=1).
    // Constraints say H, W >= 2, but robust code handles this.
    // If there are no enemies, the game is cleared instantly.
    if (total_enemies <= 0) { 
         cout << "Yes" << endl;
         return 0;
    }
    
    int defeated_count = 0; // Counter for defeated enemies

    // Keep track of visited cells. A cell is visited if it's the starting cell
    // or if the enemy there has been defeated.
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    visited[Y][X] = true; // Mark the starting cell as visited

    // Keep track of cells that are currently in either the main priority queue (main_pq)
    // or the pending priority queue (pending_pq). This prevents adding duplicate entries.
    vector<vector<bool>> in_pq(H, vector<bool>(W, false));

    // Main priority queue (min-heap): stores reachable enemies that might be defeatable.
    // Ordered by enemy attack power (ascending).
    priority_queue<PQElement, vector<PQElement>, greater<PQElement>> main_pq;
    
    // Pending priority queue (min-heap): stores reachable enemies that are currently too strong to defeat.
    // They will be reconsidered later if the player's power increases sufficiently.
    // Ordered by enemy attack power (ascending).
    priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pending_pq;

    // Define relative coordinates for neighbors (Up, Down, Left, Right)
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // Lambda function to add valid neighbors of a cell (r, c) to the main priority queue.
    // A neighbor is added if it's within grid bounds, hasn't been visited (is an enemy cell),
    // and is not already present in either priority queue.
    auto add_neighbors = [&](int r, int c) {
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // Check if the neighbor coordinates are within the grid boundaries
            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                // Check if the neighbor cell contains an undefeated enemy AND is not already queued
                if (!visited[nr][nc] && !in_pq[nr][nc]) {
                    in_pq[nr][nc] = true; // Mark this cell as being in a PQ
                    main_pq.push({A[nr][nc], {nr, nc}}); // Add the enemy to the main PQ
                }
            }
        }
    };

    // Initially, add neighbors of the starting cell to the main PQ
    add_neighbors(Y, X);

    // Main game loop: continues as long as there are enemies left to defeat
    while (defeated_count < total_enemies) {
        
        // Step 1: Check the pending queue. Move any enemies that are now defeatable
        // (due to player power increases) from pending_pq back to main_pq.
        while (!pending_pq.empty() && current_power > pending_pq.top().first) {
             main_pq.push(pending_pq.top()); // Move element
             pending_pq.pop(); // Remove from pending
        }

        // Step 2: If main_pq is empty, it means there are no reachable enemies
        // that the player can currently defeat (even after checking pending ones).
        // The player is stuck. Break the loop.
        if (main_pq.empty()) {
            break; 
        }

        // Step 3: Get the enemy with the minimum attack power from main_pq.
        PQElement top_main = main_pq.top();
        ll enemy_power = top_main.first;
        int r = top_main.second.first;
        int c = top_main.second.second;
        main_pq.pop(); // Remove this enemy from main_pq for processing

        // Safety check: If the cell retrieved from PQ is already marked as visited,
        // it means this entry is outdated (e.g., the enemy was defeated via another path).
        // Ignore this entry and continue to the next iteration.
        if (visited[r][c]) { 
             // If it was marked as in_pq, correct the flag since it's now effectively removed.
             if(in_pq[r][c]) { 
                in_pq[r][c] = false; 
             }
             continue; 
        }

        // Step 4: Attempt to battle the enemy.
        // Check if player's power is strictly greater than the enemy's attack power.
        if (current_power > enemy_power) {
            // Player wins the battle
            current_power += enemy_power; // Increase player power by enemy's attack value
            visited[r][c] = true; // Mark the cell as visited (enemy defeated)
            defeated_count++;       // Increment the count of defeated enemies
            in_pq[r][c] = false;    // Mark this cell as no longer in any PQ since it's cleared

            // Add the neighbors of the newly defeated enemy to consideration
            add_neighbors(r, c);

        } else {
            // Player cannot defeat this enemy yet (Player Power <= Enemy Attack)
            // Move this enemy to the pending_pq. It will be reconsidered later
            // if the player's power increases.
            pending_pq.push(top_main);
            // `in_pq[r][c]` remains true because the cell is now in pending_pq.
        }
    }

    // Final check after the loop terminates:
    // If the number of defeated enemies equals the total number of enemies, the game is cleared.
    if (defeated_count == total_enemies) {
        cout << "Yes" << endl;
    } else {
        // Otherwise, the player got stuck and couldn't defeat all enemies.
        cout << "No" << endl;
    }

    return 0;
}