제출 #1329855

#제출 시각아이디문제언어결과실행 시간메모리
1329855model_codeSuperpiece (EGOI22_superpiece)C++20
100 / 100
2 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
 
const int MX = 1000000000;
bool t[200];
int solve(int a, int b, int pmade = 0)
{
    if (a == 0 && b == 0)
        return 0;
    if ((a == 0 || b == 0) && t['R'])
        return 1;
    if (abs(a) == abs(b) && t['B'])
        return 1;
    if (max(abs(a), abs(b)) == 2 && min(abs(a), abs(b)) == 1 && t['N'])
        return 1;
    if (max(abs(a), abs(b)) == 1 && t['K'])
        return 1;
    if (a == 1 && b == 0 && t['P'])
        return 1;
    if (t['R'])
        return 2;
    if ((a + b) % 2 == 0 && t['B'])
        return 2;
 
    int minV = MX;
    if (t['K'])
        minV = min(minV, max(abs(a), abs(b)));
    if (t['P'] && a > 0 && b == 0)
        minV = min(minV, a);
    if (t['N'])
    {
        int da = abs(a);
        int db = abs(b);
        if (da > db)
            swap(da, db);
        int m1 = (da + db) / 3 + (da + db) % 3;
        int m2 = (db + 1) / 2;
        if (((db - 2 * da) % 4) >= 2)
            m2 += 1;
        int m = max(m1, m2);
        if (da + db == 1 || (da == 2 && db == 2))
            m += 2;
        minV = min(minV, m);
    }
    if (pmade == 0)
    {
        if (t['P'])
            minV = min(minV, solve(a - 1, b, 1) + 1);
        // cout<<minV<<'\n';
        if (t['K'])
        {
            for (int i = -2; i <= 2; i++)
            {
                for (int j = -2; j <= 2; j++)
                {
                    minV = min(minV, solve(a + i, b + j, 1) + max(abs(i), abs(j)));
                }
            }
        }
        if (t['N'])
        {
            for (int i = -2; i <= 2; i++)
            {
                for (int j = -2; j <= 2; j++)
                {
                    if (abs(i * j) == 2)
                        minV = min(minV, solve(a + i, b + j, 1) + 1);
                }
            }
        }
    }
    return minV;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    int ttt;
    cin >> ttt;
    while(ttt--) {
    string allowed;
    cin >> allowed;
    memset(t,0,sizeof(t));
    for (auto i : allowed)
    {
        t[i] = 1;
    }
    if (t['Q'])
        t['R'] = t['B'] = 1;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    c -= a;
    d -= b;
    int s = solve(c, d);
    // cout<<s<<'\n';
    cout << ((s >= MX) ? (-1) : (s)) << '\n';        
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...