概要

\(H \times W\) のグリッドから、星（T）が存在するすべての位置を見つけて、指定された順序で出力する問題です。

考察

この問題は、グリッド上の特定の文字を探索する基本的な問題です。

問題を解くための重要な気づき

1. 全探索で十分: グリッドのすべてのマスを1回ずつ確認すれば、すべての星を見つけられます
2. 出力順序の自然な保証: 行番号が小さい順、同じ行なら列番号が小さい順という条件は、グリッドを上から下へ、左から右へ走査すれば自動的に満たされます

素朴なアプローチで問題ない理由

この問題では、グリッドの各マスを1回ずつ見れば十分であり、\(H \times W \leq 1000 \times 1000 = 10^6\) 回の操作で完了します。これは十分高速なので、TLE（時間超過）の心配はありません。

具体例

例えば、以下のような \(3 \times 4\) のグリッドを考えます：

.T..
T..T
....

上から下、左から右の順に走査すると： - \((1, 2)\) で T を発見 - \((2, 1)\) で T を発見 - \((2, 4)\) で T を発見

この順序はそのまま出力順序の条件を満たしています。

アルゴリズム

1. \(H\) と \(W\) を読み込む
2. 空のリスト stars を用意する
3. 各行 \(i\)（\(1\) から \(H\)）について：
   • 文字列 \(S_i\) を読み込む
   • 各列 \(j\)（\(1\) から \(W\)）について：
     • \(S_i\) の \(j\) 番目の文字が T なら、\((i, j)\) を stars に追加
4. 星の総数（stars の長さ）を出力
5. stars の各要素を順番に出力

計算量

• 時間計算量: \(O(H \times W)\)
  • グリッドの全マスを1回ずつ走査するため
• 空間計算量: \(O(H \times W)\)
  • 最悪の場合、すべてのマスが星である可能性があるため
  • 実際には星の数 \(K\) に比例する \(O(K)\) となる

実装のポイント

1. インデックスの変換: Pythonでは配列のインデックスは0始まりですが、問題では1始まりを要求しています。そのため、出力時に i + 1 と j + 1 を使用して1始まりに変換しています。

2. 走査順序を利用: 二重ループで外側を行、内側を列としてインデックスの昇順に走査することで、特別なソートをしなくても出力順序の条件を自動的に満たします。

3. 文字列のインデックスアクセス: S[j] で文字列の \(j\) 番目の文字に直接アクセスできます。Pythonでは文字列も配列のようにインデックスでアクセス可能です。

   ソースコード

H, W = map(int, input().split())

stars = []
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == 'T':
            stars.append((i + 1, j + 1))

print(len(stars))
for r, c in stars:
    print(r, c)

---

この解説は claude4.5opus によって生成されました。