Summary

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

Analysis

What we need to find is not the number of dangerous areas or their column numbers, but the row number of the topmost row that contains X. Therefore, we can solve this problem by checking each row from top to bottom to see if it contains X.

For example, suppose the town is as follows:

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

Row \(1\) does not contain X, and it is found for the first time in row \(2\), so the answer is \(2\). Row \(3\) also contains X, but this does not change the answer.

In this problem, a naive approach of checking every area is fast enough. However, if we update the answer every time we find X, it will result in the row number of the last row containing X, leading to an incorrect answer.

Therefore, we initialize a variable ans representing the answer with -1, and update it only if the answer has not been found yet. This allows us to keep the first row number where it was found.

Algorithm

1. Read \(H\) and \(W\), and set ans = -1.
2. Iterate through the row numbers \(i\) from \(1\) to \(H\) in order, and perform the following:
   • Read the string for that row.
   • If the string contains X and ans == -1, set ans = i.
3. Output ans.

Since we check from top to bottom and only record the first row found, ans will hold the minimum row number that satisfies the condition. If X is never found, the initial value -1 will be printed as is.

Complexity

• Time Complexity: \(O(HW)\)
  For each row, we check whether the string of length \(W\) contains X.
• Space Complexity: \(O(W)\)
  Instead of storing the entire town, we only store the string for the single row currently being inspected.

Implementation Notes

• In Python, you can check whether the string row contains X using 'X' in row.

• Since row numbers are \(1\)-indexed, use range(1, h + 1).

• The condition ans == -1 prevents overwriting the answer after it has already been found.

• Even after the answer is found, we continue reading the remaining rows, but ans remains unchanged.

  Source Code

# 問題文から独立に実装
h, w = map(int, input().split())
ans = -1
for i in range(1, h + 1):
    row = input()
    if 'X' in row and ans == -1:
        ans = i
print(ans)

---

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