概要

上の行から順に調べ、X が初めて現れる行の番号を求めます。どの行にも X がなければ -1 を出力します。

考察

求めるのは、X を含む行のうち、最も上にある行です。そのため、上から順に各行を調べ、X を含む行を見つけた時点で、その行番号を出力すればよいです。

例えば、町の様子が次の場合を考えます。

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

\(1\) 行目には X がなく、\(2\) 行目には X があります。したがって答えは \(2\) です。\(3\) 行目にも X がありますが、最初に見つかる行ではないので考慮する必要はありません。

この問題では、すべての区域を素朴に調べても最大 \(10 \times 10 = 100\) 区域なので、TLE にはなりません。一方、X を見つけるたびに答えを上書きすると、最後に X が現れる行を出力してしまう可能性があります。最初に条件を満たした行で処理を終了することで、これを防げます。

アルゴリズム

1. \(H, W\) を読み取ります。
2. 行番号 \(i\) を \(1\) から \(H\) まで順に動かし、次の処理を行います。
   • その行の文字列を読み取ります。
   • 行内の各文字を調べ、X の個数を cnt に数えます。
   • cnt が \(0\) より大きければ、\(i\) を出力してプログラムを終了します。
3. 最後まで X を含む行が見つからなければ、-1 を出力します。

行を上から順に調べているため、cnt が初めて正になった行より上には X がありません。よって、その行が調査を始める行です。また、すべての行で cnt が \(0\) なら、町全体に X がないため、-1 が正しい答えです。

計算量

• 時間計算量: \(O(HW)\)
  最悪の場合、\(H\) 行それぞれについて \(W\) 文字を調べます。
• 空間計算量: \(O(W)\)
  長さ \(W\) の文字列を \(1\) 行分だけ保持します。

実装のポイント

• 出力する行番号は \(1\) 始まりなので、外側のループは i = 1 から始めます。

• C++ の文字列の添字は \(0\) 始まりなので、文字を調べるループは j = 0 から j < w までとします。

• cnt は行ごとに 0 に初期化します。

• 答えを出力した直後に return 0; で終了することで、後の行を調べたり、最後の -1 を出力したりすることを防ぎます。

  ソースコード

// 問題文から独立に実装: 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;
}

---

この解説は gpt-6-astra-medium によって生成されました。