Peli

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

bool dp[101][101][4];
bool done[101][101][4];
int n;

bool solve(int a, int b, int c, bool firstmove) {
    if (done[a][b][c]) return dp[a][b][c];
    if (!firstmove && a == 0 && b == 1) return false;
    if (!firstmove && a == n-2 && b == n-1) return false;
    if (!firstmove) done[a][b][c] = true;
    if (a > 0) {
        if (c != 0 || firstmove) {
            if (!solve(a-1,b,1,false)) {
                dp[a][b][c] = true;
                return true;
            }
        }
    }
    if (b > a+1) {
        if (c != 1 || firstmove) {
            if (!solve(a+1,b,0,false)) {
                dp[a][b][c] = true;
                return true;
            }
        }
        
        if (c != 2 || firstmove) {
            if (!solve(a,b-1,3,false)) {
                dp[a][b][c] = true;
                return true;
            }
        }
    }
    if (b < n-1) {
        if (c != 3 || firstmove) {
            if (!solve(a,b+1,2,false)) {
                dp[a][b][c] = true;
                return true;
            }
        }
    }
    dp[a][b][c] = false;
    return false;
}

void testCase() {           
    string str;
    cin >> str;
    n = str.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                done[i][j][k] = false;
                dp[i][j][k] = false;
            }
        }
    }
    if (n == 2) {
        cout << 2 << "\n";
        return;
    }
    int a = -1, b = -1;
    for (int i = 0; i < n; i++) {
        if (str[i] == 'P') {
            if (a == -1) a = i;
            else b = i;
        }
    }
    if (solve(a,b,0,true)) cout << 1 << "\n";
    else cout << 2 << "\n";
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        testCase();
    }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: WRONG ANSWER