Since each row is independent, it is sufficient to solve for \(H=1\). This problem can be solved with a greedy algorithm.

Specifically, inspect \(S\) from the left. If two T’s occur consecutively, replace them with PC. This is valid because it achieves the maximum bound of the number of an operation of replacing with PC. (When \(K\) T’s occur consecutively, the operation can be done at most \(\lfloor\frac{K}{2}\rfloor\) times; this algorithm achieves the upper bound.)

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    for(int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < w - 1; j++) {
            if(s[j] == 'T' and s[j + 1] == 'T') {
                s[j] = 'P';
                s[j + 1] = 'C';
            }
        }
        cout << s << endl;
    }
}