Overview

This problem asks you to find all positions containing stars (T) in an \(H \times W\) grid and output them in a specified order.

Analysis

This problem is a basic problem of searching for specific characters on a grid.

Key Observations for Solving the Problem

1. Brute force is sufficient: By checking each cell of the grid exactly once, we can find all stars
2. Output order is naturally guaranteed: The condition of outputting in ascending order of row number, and for the same row, in ascending order of column number, is automatically satisfied by scanning the grid from top to bottom and left to right

Why a Naive Approach Works

In this problem, it’s sufficient to look at each cell of the grid exactly once, completing in \(H \times W \leq 1000 \times 1000 = 10^6\) operations. This is fast enough, so there’s no concern about TLE (Time Limit Exceeded).

Concrete Example

For example, consider the following \(3 \times 4\) grid:

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

Scanning from top to bottom, left to right: - Found T at \((1, 2)\) - Found T at \((2, 1)\) - Found T at \((2, 4)\)

This order directly satisfies the output order requirements.

Algorithm

1. Read \(H\) and \(W\)
2. Prepare an empty list stars
3. For each row \(i\) (from \(1\) to \(H\)):
   • Read string \(S_i\)
   • For each column \(j\) (from \(1\) to \(W\)):
     • If the \(j\)-th character of \(S_i\) is T, add \((i, j)\) to stars
4. Output the total number of stars (length of stars)
5. Output each element of stars in order

Complexity

• Time complexity: \(O(H \times W)\)
  • Because we scan each cell of the grid exactly once
• Space complexity: \(O(H \times W)\)
  • In the worst case, all cells could be stars
  • In practice, it’s \(O(K)\) proportional to the number of stars \(K\)

Implementation Notes

1. Index conversion: In Python, array indices are 0-based, but the problem requires 1-based indexing. Therefore, we use i + 1 and j + 1 when outputting to convert to 1-based indices.

2. Utilizing scan order: By using a nested loop with the outer loop for rows and the inner loop for columns, scanning in ascending order of indices, the output order requirement is automatically satisfied without any special sorting.

3. String index access: We can directly access the \(j\)-th character of a string with S[j]. In Python, strings can be accessed by index just like arrays.

   Source Code

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)

---

This editorial was generated by claude4.5opus.