概要

各行に宝物を表す T が含まれているかを調べます。含まれていれば o、含まれていなければ x を、上の行から順に並べて出力します。

考察

ある行の答えを決めるには、その行だけを調べれば十分です。他の行に宝物があるかどうかは関係ありません。

そこで、各行の文字をすべて確認し、T の個数を数えます。

• T が \(0\) 個なら、宝物がないので x
• T が \(1\) 個以上なら、宝物があるので o

例えば、行が ..T.T なら T は \(2\) 個あるため o、..... なら \(0\) 個なので x です。

この問題では、すべてのマスを調べる素朴な方法で十分です。マス数は最大でも \(10 \times 10 = 100\) 個なので、時間制限を超える心配はありません。なお、宝物が「ちょうど \(1\) 個」の場合だけ o にすると、複数ある行で誤答になるため注意しましょう。

アルゴリズム

1. \(H\) と \(W\) を読み込み、答えを格納する空の文字列 ans を用意します。
2. 上の行から順に、次の処理を行います。
   1. その行の文字列 s を読み込みます。
   2. 宝物の個数を表す cnt を \(0\) にします。
   3. s の \(W\) 文字を調べ、T が見つかるたびに cnt を \(1\) 増やします。
   4. cnt が \(0\) なら ans に x、そうでなければ o を追加します。
3. ans を出力します。

各行のすべての文字を確認するため、cnt はその行にある宝物の個数と一致します。また、上から順に判定結果を追加するので、求める長さ \(H\) の文字列が得られます。

計算量

• 時間計算量: \(O(HW)\)
  \(H\) 行それぞれについて、\(W\) 文字を調べます。
• 空間計算量: \(O(H + W)\)
  長さ \(H\) の答え ans と、長さ \(W\) の処理中の行 s を保持します。

実装のポイント

• cnt は行ごとに \(0\) に戻します。前の行の個数を引き継がないようにしましょう。

• 文字列の添字は \(0\) から始まるため、s[0] から s[W-1] までを調べます。

• 出力するのは小文字の o と x です。数字の 0 や大文字の O と間違えないようにしましょう。

• 地図全体を保存する必要はなく、\(1\) 行ずつ読み込んで処理できます。

  ソースコード

// 問題文から独立に実装: 各行の 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;
}

この解説は gpt-6-astra-medium によって生成されました。