Overview

We inspect the rows from top to bottom to find the index of the first row where X appears. If no row contains X, we output -1.

Analysis

What we need to find is the topmost row among those containing X. Therefore, we can inspect each row from top to bottom and output the row index as soon as we find a row containing X.

For example, consider the following layout of the town:

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

Row \(1\) does not contain X, and Row \(2\) contains X. Thus, the answer is \(2\). Row \(3\) also contains X, but we do not need to consider it because it is not the first row found.

In this problem, naively checking all cells takes at most \(10 \times 10 = 100\) cells, so it will not cause a TLE. On the other hand, if you overwrite the answer every time you find an X, you might end up outputting the last row where X appears. You can prevent this by terminating the process at the first row that satisfies the condition.

Algorithm

1. Read \(H\) and \(W\).
2. Iterate the row index \(i\) from \(1\) to \(H\) and perform the following:
   • Read the string for that row.
   • Inspect each character in the row and count the number of X’s in cnt.
   • If cnt is greater than \(0\), output \(i\) and terminate the program.
3. If no row containing X is found by the end, output -1.

Since we check the rows from top to bottom, there is no X above the row where cnt first becomes positive. Therefore, that row is where the investigation should begin. Furthermore, if cnt is \(0\) for all rows, there is no X in the entire town, so -1 is the correct answer.

Complexity

• Time complexity: \(O(HW)\)
  In the worst case, we inspect \(W\) characters for each of the \(H\) rows.
• Space complexity: \(O(W)\)
  We only need to store a single row’s string of length \(W\) at a time.

Implementation Details

• Since the row index to output is 1-based, start the outer loop from i = 1.

• Since string indexing in C++ is 0-based, the loop for checking characters should run from j = 0 to j < w.

• Reset cnt to 0 for each row.

• By terminating with return 0; immediately after outputting the answer, you avoid checking subsequent rows and prevent erroneously outputting the final -1.

  Source Code

// 問題文から独立に実装: X の個数を数えて最初に正になった行で終了
#include <iostream>
#include <string>
int main() {
    int h, w; std::cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        std::string s; std::cin >> s;
        int cnt = 0;
        for (int j = 0; j < w; ++j) if (s[j] == 'X') cnt++;
        if (cnt > 0) { std::cout << i << std::endl; return 0; }
    }
    std::cout << -1 << std::endl;
}

---

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