Overview

Check whether each row contains a T representing a treasure. If it contains a treasure, output o; otherwise, output x, listed in order from the top row to the bottom row.

Analysis

To determine the answer for a particular row, it is sufficient to inspect only that row. Whether other rows contain treasures is irrelevant.

Therefore, we check all characters in each row and count the number of Ts.

• If the count of T is \(0\), there is no treasure, so the answer is x.
• If the count of T is \(1\) or more, there is a treasure, so the answer is o.

For example, if a row is ..T.T, there are \(2\) Ts, so it is o; if it is ....., there are \(0\) Ts, so it is x.

For this problem, a naive approach of checking every cell is sufficient. Since there are at most \(10 \times 10 = 100\) cells, there is no need to worry about exceeding the time limit. Note that if you set the answer to o only when there is “exactly \(1\)” treasure, rows with multiple treasures will result in a Wrong Answer, so be careful.

Algorithm

1. Read \(H\) and \(W\), and initialize an empty string ans to store the answer.
2. From the top row to the bottom, perform the following steps:
   1. Read the string s for that row.
   2. Reset cnt, which represents the number of treasures, to \(0\).
   3. Check all \(W\) characters of s, and increment cnt by \(1\) each time a T is found.
   4. If cnt is \(0\), append x to ans; otherwise, append o.
3. Output ans.

Since we check all characters in each row, cnt matches the number of treasures in that row. Furthermore, because we append the results from top to bottom, we obtain the required string of length \(H\).

Complexity

• Time complexity: \(O(HW)\)
  For each of the \(H\) rows, we inspect \(W\) characters.
• Space complexity: \(O(H + W)\)
  We store the answer ans of length \(H\) and the current row s of length \(W\).

Implementation Notes

• Reset cnt to \(0\) for each row. Make sure not to carry over the count from the previous row.

• Since string indexing is \(0\)-based, check indices from s[0] to s[W-1].

• The output requires lowercase o and x. Be careful not to confuse them with the digit 0 or uppercase O.

• There is no need to store the entire grid; you can process it by reading \(1\) row at a time.

  Source Code

// 問題文から独立に実装: 各行の T の個数を数え、0 なら x
#include <iostream>
#include <string>
int main() {
    int h, w; std::cin >> h >> w;
    std::string ans;
    for (int i = 0; i < h; ++i) {
        std::string s; std::cin >> s;
        int cnt = 0;
        for (int j = 0; j < w; ++j) if (s[j] == 'T') cnt++;
        ans += (cnt == 0) ? 'x' : 'o';
    }
    std::cout << ans << std::endl;
}

This editorial was generated by gpt-6-astra-medium.