Overview

Given an \(H\)-row by \(W\)-column grid-shaped image, the task is to identify the positions (row number and column number) of all cells containing the character 'T' representing a star, and output them in the specified order.

Analysis

What this problem requires is to check every cell in the grid and record the coordinates of cells where 'T' is found.

The two important points are as follows:

1. Output order: The output must be in “ascending order of row number, and for the same row number, ascending order of column number.”
   • If we scan the grid from top to bottom (row number \(1 \to H\)) and left to right (column number \(1 \to W\)), the coordinates are naturally found in this order. Therefore, no special sorting is needed.
2. Index conversion: In the program, array indices typically start from 0, but the problem statement specifies that the top-left cell is \((1, 1)\). We need to add +1 to both the row number and column number when outputting.

Checking the constraints, \(H, W \leq 1000\), so the total number of cells is at most \(1,000,000\) (one million). A straightforward implementation (brute-force search) that checks each cell once is well within the time limit.

Algorithm

1. Read the number of rows \(H\) and number of columns \(W\) of the grid.
2. Read each row’s string \(S_i\) in order.
3. Use a nested loop to examine each cell \((r, c)\).
   • Outer loop: iterate row number \(r\) from \(0\) to \(H-1\).
   • Inner loop: iterate column number \(c\) from \(0\) to \(W-1\).
4. If the character at cell \((r, c)\) is 'T', add the position \((r+1, c+1)\) to a list.
5. Finally, output the length of the list (the total number of stars \(K\)), then output the recorded coordinates in order.

Complexity

• Time complexity: \(O(H \times W)\)
  • Since we check every cell of the grid exactly once, the time is proportional to the number of cells. This is at most about \(10^6\) operations, which runs efficiently.
• Space complexity: \(O(H \times W)\)
  • Memory proportional to the grid size is used to store the input data and star positions.

Implementation Notes

• Efficient I/O: When outputting a large amount of data in Python, rather than calling print many times, it is faster to store results in a list and output them all at once using '\n'.join().

• Conversion to 1-indexed: The 0, 1, 2, ... indices used within the program are converted to match the problem statement’s specification by using r + 1, c + 1 at output time.

  Source Code

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

This editorial was generated by gemini-3-flash-preview.