概要

\(H \times W\) のグリッドから T（星）があるマスをすべて見つけ、座標 \((行, 列)\) を上から順・左から順に列挙して出力する問題です。

考察

• 各マスは . か T のどちらかなので、「全マスを一度ずつ見て T を見つける」だけで十分です。
• 出力順は「行番号が小さい順、同じ行なら列番号が小さい順」ですが、グリッドを上の行から順に、各行を左から順に走査すれば、その走査順＝要求される出力順になります。したがって、後からソートする必要はありません。
• 素朴に「T の位置を集めて最後にソートする」方法でも正解はできますが、ソートに \(O(K \log K)\) かかり不要です（\(K\) は星の数）。今回は走査順にそのまま出せるため、よりシンプルに \(O(HW)\) で処理できます。
• 出力形式上、最初に星の総数 \(K\) を出す必要があります。そのため、
  • 先に全体を数える（1回目の走査）→ \(K\) を出力
  • もう一度走査して座標を出力（2回目の走査） という形にすると実装が簡単です。
    例：
    

  .T.
  TT.
  

  なら、走査順に (1,2), (2,1), (2,2) と出せば条件通りです。

アルゴリズム

1. 入力として文字列配列 \(S_1 \ldots S_H\) を受け取る。
2. 各行の T の個数を数えて合計し、星の総数 \(K\) を求めて出力する。
3. \(r=1..H\) の順に各行を、さらに \(c=1..W\) の順に各文字を調べる。
4. \(S_r[c]\) が T なら、その座標 \((r, c)\) を出力する。
   （この走査順がそのまま要求される出力順になる。）

計算量

• 時間計算量: \(O(HW)\)（全マスを定数回見るだけ）
• 空間計算量: \(O(HW)\)（入力グリッドを保持する分）

実装のポイント

• 座標は \((1,1)\) 始まりなので、enumerate(..., 1) を使うとミスが減ります。

• \(H, W \le 1000\) なので最大 \(10^6\) マスを扱います。Pythonでは sys.stdin.readline を使って高速に読み込み、出力も sys.stdout.write を使うと安心です。

• 1行目に \(K\) を出す必要があるため、先に count('T') で合計を求めてから座標を列挙しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = [input().rstrip('\n') for _ in range(H)]

    K = sum(row.count('T') for row in S)
    out = sys.stdout.write
    out(str(K) + "\n")

    for r, row in enumerate(S, 1):
        for c, ch in enumerate(row, 1):
            if ch == 'T':
                out(f"{r} {c}\n")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。