#include #include #include #include // For std::pair #include // 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>; 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> A(H, vector(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> visited(H, vector(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> in_pq(H, vector(W, false)); // Main priority queue (min-heap): stores reachable enemies that might be defeatable. // Ordered by enemy attack power (ascending). priority_queue, greater> 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, greater> 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; }