Overview

In each operation, we toggle the light bulbs at the pressed switch’s cell and its adjacent cells (up, down, left, right). Since at most \(5\) cells are affected, we can solve this problem by simply simulating each operation in order.

Analysis

The key point is that pressing a switch once changes the state of at most \(5\) light bulbs.

If we check every cell in each operation to determine whether it should be toggled, the time complexity would be \(O(QHW)\). Under the maximum constraints, this would require around \(10^{11}\) checks, which will result in Time Limit Exceeded (TLE).

Instead, we can directly inspect only the pressed cell and its adjacent cells (up, down, left, and right). This way, we check at most \(5\) cells per operation.

For example, in a \(3 \times 3\) grid, pressing the switch at \((1,1)\) toggles the following \(3\) cells:

• The pressed cell \((1,1)\)
• The cell below \((2,1)\)
• The cell to the right \((1,2)\)

Since there are no cells above or to the left, we do nothing for those directions. Thus, we need to check whether a cell is within the grid bounds before toggling it.

Also, toggling the same light bulb twice returns it to its original state. Even if the same switch is pressed multiple times, toggling it each time correctly handles the state without any special logic needed.

Algorithm

1. Store the initial state in an array of strings \(S\).
2. Process the \(Q\) operations in the order they are given:
   1. Read the switch coordinates and subtract \(1\) from both the row and column to match 0-indexed arrays.
   2. Check the following \(5\) relative positions from the pressed cell:
      • Itself: \((0,0)\)
      • Up: \((-1,0)\)
      • Down: \((1,0)\)
      • Left: \((0,-1)\)
      • Right: \((0,1)\)
   3. If the target cell is within the bounds of the grid, flip the character from 0 to 1 or from 1 to 0.
3. After finishing all operations, output \(S\) line by line.

In each operation, exactly the cells specified by the problem statement are toggled once. Therefore, \(S\) always represents the current state of the light bulbs after each operation, and the final \(S\) output at the end is the desired answer.

Complexity

• Time Complexity: \(O(HW + Q)\)
  • Reading the initial state and printing the final state takes \(O(HW)\).
  • Each operation checks at most \(5\) cells, taking \(O(Q)\) in total across all operations.
• Space Complexity: \(O(HW)\)
  • We maintain the state of the light bulbs as an array of strings. Operations are processed as they are read, so there is no need to store them.

Implementation Points

• Convert to 0-based indexing
  The input is 1-based, but arrays and strings in C++ are 0-based. In the code, this is converted using --r; --c;.

• Include the cell itself in the direction arrays
  By placing 0 at the beginning of dr and dc, the pressed cell itself can be processed within the same loop.

• Check bounds before accessing the array
  Letting the target coordinates be \((nr,nc)\), toggle only if \(0 \leq nr < H\) and \(0 \leq nc < W\). This properly handles border cells and cases where \(H=1\) or \(W=1\).

• Toggle as characters
  Since each element of \(S\) is a character, use the characters '0' and '1' rather than the numerical values 0 and 1.

  Source Code

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    for (auto& row : S) cin >> row;

    int Q;
    cin >> Q;

    constexpr int dr[] = {0, -1, 1, 0, 0};
    constexpr int dc[] = {0, 0, 0, -1, 1};

    while (Q--) {
        int r, c;
        cin >> r >> c;
        --r;
        --c;

        for (int d = 0; d < 5; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (0 <= nr && nr < H && 0 <= nc && nc < W) {
                S[nr][nc] = (S[nr][nc] == '0' ? '1' : '0');
            }
        }
    }

    for (const auto& row : S) cout << row << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.