概要

\(H\) 行 \(W\) 列のグリッド状の画像から、星を表す文字 'T' が含まれるすべてのマスの位置（行番号と列番号）を特定し、指定された順序で出力する問題です。

考察

この問題で求められているのは、グリッド内のすべてのマスを確認し、'T' が見つかったマスの座標を記録することです。

重要なポイントは以下の2点です。

1. 出力の順序: 「行番号が小さい順、行番号が同じ場合は列番号が小さい順」に出力する必要があります。
   • グリッドを上から下（行番号 \(1 \to H\)）、左から右（列番号 \(1 \to W\)）の順で走査すれば、自然にこの順序で座標を見つけることができます。そのため、特別なソート処理は不要です。
2. インデックスの変換: プログラム上では配列の添字は通常 0 から始まりますが、問題文では左上のマスを \((1, 1)\) とするように指定されています。出力時に行番号と列番号にそれぞれ +1 する必要があります。

制約を確認すると \(H, W \leq 1000\) であり、全マス数は最大で \(1,000,000\)（100万）マスです。すべてのマスを1回ずつ確認する素直な実装（全探索）で、制限時間内に十分間に合います。

アルゴリズム

1. グリッドの行数 \(H\) と列数 \(W\) を読み込みます。
2. 各行の文字列 \(S_i\) を順番に読み込みます。
3. 二重ループを用いて、各マス \((r, c)\) を調べます。
   • 外側のループ：行番号 \(r\) を \(0\) から \(H-1\) まで繰り返す。
   • 内側のループ：列番号 \(c\) を \(0\) から \(W-1\) まで繰り返す。
4. もしマス \((r, c)\) の文字が 'T' であれば、その位置 \((r+1, c+1)\) をリストに追加します。
5. 最後に、リストの長さ（星の総数 \(K\)）を出力し、記録した座標を順番に出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • グリッドのすべてのマスを一度ずつ確認するため、マス数に比例した時間がかかります。最大で \(10^6\) 程度の操作であり、高速に動作します。
• 空間計算量: \(O(H \times W)\)
  • 入力データおよび星の位置を保持するために、グリッドのサイズに比例したメモリを使用します。

実装のポイント

• 効率的な入出力: Pythonで大量のデータを出力する場合、print を何度も呼び出すよりも、結果をリストに格納して最後に '\n'.join() で一気に出力する方が実行時間を短縮できます。

• 1-indexed への変換: プログラム内の 0, 1, 2, ... という添字を、出力時に r + 1, c + 1 とすることで問題文の指定に合わせます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字（スペース、改行など）で分割してリストに格納します。
    # これにより、H, W および各行の文字列 Si を効率的に取得できます。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了します。
    if not input_data:
        return
    
    # 1番目の要素が行数 H、2番目の要素が列数 W です。
    H = int(input_data[0])
    W = int(input_data[1])
    
    # 各行の文字列は input_data[2] から input_data[H+1] までに格納されています。
    # 星（'T'）の位置を格納するためのリストを用意します。
    stars = []
    
    # 各行を順番に走査します。
    for r in range(H):
        # r行目の文字列を取得します。
        row_str = input_data[r + 2]
        
        # 文字列内の各文字を順番に走査します。
        for c in range(W):
            # 文字が 'T' であれば、その位置を記録します。
            if row_str[c] == 'T':
                # 問題文の指示通り、1-indexed（1から始まる番号）で保存します。
                # 行番号 r+1, 列番号 c+1 となります。
                # 行番号が小さい順、次に列番号が小さい順に探索しているため、
                # リストには自動的にソートされた状態で追加されます。
                stars.append(f"{r + 1} {c + 1}")
    
    # 最初に星の総数 K を出力します。
    print(len(stars))
    
    # 星が存在する場合、各星の位置を改行区切りで一気に出力します。
    if stars:
        print('\n'.join(stars))

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。