解説

各行について T が含まれるかを調べ、含まれれば o、なければ x を出力に追加します。プログラムでは文字列 s に対して s.find('T') を呼び、見つからなかったことを示す string::npos が返るかどうかで判定しています。find は行の先頭から順に T を探すので、その行に宝物があるかどうかを正確に判定でき、これを上の行から順に繰り返せば答えの文字列が完成します。

各行の走査は \(O(W)\) 時間で、これを \(H\) 行分行うため計算時間は \(O(HW)\) です。一度に保持するのは1行分の文字列 \(O(W)\) と答えの文字列 \(O(H)\) なので、入出力を含めた使用メモリは \(O(H + W)\)(読んだ入力全体を数えても \(O(HW)\))です。