Overview

We inspect each row from top to bottom to find the row number of the first row containing X. If no row contains X, output -1.

Analysis

Whether a row contains a hazardous zone can be determined by checking if the string for that row contains X. In Python, this check can be done with 'X' in s.

What we want to find is the topmost row among those containing a hazardous zone. Therefore, we can inspect the rows from top to bottom and terminate the search as soon as we find the first X. There is no need to examine any rows below it.

For example, consider the case where the rows are as follows:

....
..X.
X...

Row \(1\) does not contain X, and Row \(2\) contains X, so the answer is \(2\). Although Row \(3\) also contains X, it does not affect the answer.

In this problem, even a naive approach that checks every cell requires at most \(HW \leq 100\) checks, so it will not result in TLE. However, if you overwrite the answer every time you find an X and continue searching until the end, you will end up outputting the bottommost matching row. It is important to break as soon as you find the first one.

Algorithm

1. Initialize the variable ans representing the answer to -1.
2. Inspect each row from top to bottom along with its row number \(i = 1, 2, \ldots, H\).
   • If that row contains X, assign \(i\) to ans and terminate the search.
3. Output ans.

Since we inspect from top to bottom, there are no hazardous zones above the row where X is first found. Therefore, that row is where the investigation should begin. Additionally, if no row contains X, ans remains -1, correctly outputting the expected result.

Complexity

• Time Complexity: \(O(HW)\)
  Checking whether each row contains X takes at most \(O(W)\) time, which is done for at most \(H\) rows. Including reading the input, the time complexity is \(O(HW)\).
• Space Complexity: \(O(HW)\)
  The provided code reads the entire input and stores the string for each row. The additional variables used during the search take \(O(1)\) space.

Implementation Details

• Using enumerate(rows, start=1) allows you to directly obtain the \(1\)-based row numbers required by the problem.

• Initializing with ans = -1 allows you to handle the case where there are no hazardous zones without any special conditional branches.

• Once X is found, break to preserve the first row number encountered.

• Since you can check the entire string using 'X' in s, there is no need to directly use the number of columns \(W\) during the search process.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    H = int(data[0])
    # W = int(data[1])  # unused
    rows = data[2:2 + H]
    ans = -1
    for i, s in enumerate(rows, start=1):
        if 'X' in s:
            ans = i
            break
    print(ans)

main()

---

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