Overview

This problem asks you to find all cells containing T (stars) in an \(H \times W\) grid, and output their coordinates \((row, column)\) in order from top to bottom, and left to right.

Analysis

• Since each cell is either . or T, it suffices to simply “look at every cell once and find the Ts.”
• The output order is “ascending by row number, and for the same row, ascending by column number.” If we scan the grid from the top row downward and each row from left to right, the scan order exactly matches the required output order. Therefore, no sorting is needed afterward.
• A naive approach of “collecting all T positions and sorting at the end” would also produce the correct answer, but the sorting costs an unnecessary \(O(K \log K)\) (where \(K\) is the number of stars). Since we can output in scan order directly, we can handle this more simply in \(O(HW)\).
• The output format requires printing the total number of stars \(K\) first. Therefore, a straightforward implementation is:
  • First, count the total across the entire grid (1st scan) → output \(K\)
  • Then scan again and output the coordinates (2nd scan)

Example:

  .T.
  TT.

In this case, outputting (1,2), (2,1), (2,2) in scan order satisfies the requirements.

Algorithm

1. Read the input as a string array \(S_1 \ldots S_H\).
2. Count the number of Ts in each row, sum them up, compute the total number of stars \(K\), and output it.
3. For each row in order \(r=1..H\), and for each character in order \(c=1..W\), examine each cell.
4. If \(S_r[c]\) is T, output the coordinate \((r, c)\). (This scan order directly matches the required output order.)

Complexity

• Time complexity: \(O(HW)\) (each cell is visited a constant number of times)
• Space complexity: \(O(HW)\) (for storing the input grid)

Implementation Notes

• Coordinates are 1-indexed starting from \((1,1)\), so using enumerate(..., 1) helps avoid off-by-one errors.

• Since \(H, W \le 1000\), we handle up to \(10^6\) cells. In Python, using sys.stdin.readline for fast input and sys.stdout.write for output is recommended for safety.

• Since \(K\) must be printed on the first line, we first compute the total using count('T') before enumerating the coordinates.

  Source Code

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

This editorial was generated by gpt-5.2-high.