概要

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

考察

ある行に危険な区域があるかどうかは、その行の文字列に X が含まれているかで判断できます。Python では、'X' in s でこの判定ができます。

求めたいのは、危険な区域がある行のうち最も上にある行です。そのため、上から順に調べて最初に X を見つけた時点で探索を終了すればよいです。それより下の行を調べる必要はありません。

例えば、各行が次のようになっている場合を考えます。

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

\(1\) 行目には X がなく、\(2\) 行目には X があるので、答えは \(2\) です。\(3\) 行目にも X がありますが、答えには影響しません。

この問題は、すべての区域を確認する素朴な方法でも最大 \(HW \leq 100\) 個の確認で済み、TLE にはなりません。ただし、X を見つけるたびに答えを上書きして最後まで探索すると、最も下の該当行を答えてしまいます。最初に見つけたところで break することが重要です。

アルゴリズム

1. 答えを表す変数 ans を -1 に初期化します。
2. 各行を上から順に、行番号 \(i = 1, 2, \ldots, H\) とともに調べます。
   • その行に X が含まれていれば、ans に \(i\) を代入し、探索を終了します。
3. ans を出力します。

上から順に調べているため、最初に X が見つかった行より上には危険な区域がありません。したがって、その行が調査を始める行です。また、どの行にも X がなければ ans は -1 のままなので、正しい結果を出力できます。

計算量

• 時間計算量: \(O(HW)\)
  各行の X の有無を調べるのに最大 \(O(W)\) かかり、それを最大 \(H\) 行について行います。入力の読み込みも含めて \(O(HW)\) です。
• 空間計算量: \(O(HW)\)
  提示コードでは入力全体を読み込み、各行の文字列を保持します。探索で使う追加の変数は \(O(1)\) です。

実装のポイント

• enumerate(rows, start=1) を使うと、問題で求められる \(1\) 始まりの行番号をそのまま取得できます。

• ans = -1 と初期化しておくことで、危険な区域がない場合も特別な分岐なしで処理できます。

• X を見つけたら break し、最初に見つけた行番号を保持します。

• 文字列全体に対して 'X' in s で判定できるため、列数 \(W\) を探索処理で直接使う必要はありません。

  ソースコード

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()

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