QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640100#2924. Lone Rookenze114514AC ✓5767ms37896kbC++204.3kb2024-10-14 04:58:272024-10-14 04:58:27

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 04:58:27]
  • 评测
  • 测评结果:AC
  • 用时:5767ms
  • 内存:37896kb
  • [2024-10-14 04:58:27]
  • 提交

answer

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

#define pb push_back

const ld pi = 3.14159265358979323846;
const int mod = 998244353;
const ll INF = 1e18;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const int N = (int)1e5 + 1, M = N * 2;

int jpx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}, jpy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int dirx[4] = {1, -1, 0, 0}, diry[4] = {0, 0, 1, -1};

void solve(){
    int n, m;
    cin >> n >> m;

    char c[n][m];
    vector<vector<int>> d(n, vector<int>(m, 0)), v(n, vector<int>(m, 0));

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            v[i][j] = d[i][j] = 0;
            c[i][j] = s[j];
        }
    }

    map<pair<int, int>, int> mp;
    auto set = [&](int q, int p, int op) -> void{
         for(int i = 0; i < 8; i++){
            int x = q + jpx[i], y = p + jpy[i];
            if(x < 0 || y < 0 || x >= n || y >= m){
                continue;
            }
            d[x][y] += op;
         }
    };

    queue<pair<int, int>> q;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(c[i][j] == 'R'){
                q.push({i, j});
                v[i][j] = 1;
            }
            if(c[i][j] == 'K'){
                set(i, j, 1);
            }
        }
    }
 
    // for(int i = 0; i < n; i++){
    //     for(int j = 0; j < m; j++){
    //         cout << d[i][j] << " ";
    //     } cout << endl;
    // }

    while(!q.empty()){
        auto p = q.front();
        q.pop();
        int x = p.first, y = p.second;

        queue<pair<int, int>> hr;

        for(int i = 0; i < 4; i++){
            int dx = x + dirx[i], dy = y + diry[i];
            while(dx >= 0 && dy >= 0 && dx < n && dy < m){
                if(v[dx][dy]){

                }
                else if(d[dx][dy]){
                    mp[{dx, dy}] = 1;
                    if(c[dx][dy] == 'K'){
                        break;
                    }
                }
                else{
                    if(c[dx][dy] == 'K'){
                        hr.push({dx, dy});
                        break;
                    }
                    else if(c[dx][dy] == 'T'){
                        cout << "yes" << endl;
                        return;
                    }
                    else{
                        v[dx][dy] = 1;
                        q.push({dx, dy});
                        // cout << "first " << dx << " " << dy << " " << v[dx][dy] << endl;
                    }
                }
                dx += dirx[i], dy += diry[i];
            }
        }
        // cout << q.size() << endl;

        while(!hr.empty()){
            auto kn = hr.front();
            hr.pop();

            int nx = kn.first, ny = kn.second;
            c[nx][ny] = '.';
            v[nx][ny] = 1;

            q.push({nx, ny});
            // cout << "second " << nx << " " << ny << endl;
            set(nx, ny, -1);

            for(int i = 0; i < 8; i++){
                int dx = nx + jpx[i], dy = ny + jpy[i];
                if(dx < 0 || dy < 0 || dx >= n || dy >= m) continue;
                if(v[dx][dy]) continue;
                if(!d[dx][dy] && mp[{dx, dy}]){
                    mp[{dx, dy}] = 0;
                    if(c[dx][dy] == 'K'){
                        hr.push({dx, dy});
                    }
                    else{
                        if(c[dx][dy] == 'T'){
                            cout << "yes" << endl;
                            return;
                        }
                        c[dx][dy] = '.';
                        v[dx][dy] = 1;
                        q.push({dx, dy});
                        // cout << "third " << dx << " " << dy << endl;
                    }
                }
            }
        }
        // cout << q.size() << endl;
    }
    cout << "no" << endl;
}

int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
//    cin >> t;

    while(t--){
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

5 3
KKT
.K.
K..
...
KKR

output:

yes

result:

ok single line: 'yes'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

2 5
RKKK.
...KT

output:

no

result:

ok single line: 'no'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

5 6
.....T
..K...
..KK..
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 4
...K
T.KR
..K.

output:

no

result:

ok single line: 'no'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

6 3
.R.
...
...
KKK
.K.
.T.

output:

yes

result:

ok single line: 'yes'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

6 6
..K..T
..K...
......
..KK.K
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

6 6
..K...
..KTK.
......
..KK..
...K..
R.....

output:

yes

result:

ok single line: 'yes'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

14 6
T.K..K
......
K....K
KKK.KK
KKK.KK
......
......
..K.KK
.K...K
......
..KK.K
...K..
......
R.K.K.

output:

yes

result:

ok single line: 'yes'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

9 12
R...K.....KK
...KKK.T..KK
...K......KK
...K......KK
.....K....KK
..........KK
KK.......KKK
.KK...K..KKK
..K......KKK

output:

yes

result:

ok single line: 'yes'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

17 14
......KK......
......KK......
RKK...KK......
K.....KKKK...K
......KKKK..KK
......KKKK..KK
...KKKKK.....K
..K.KKKKK.....
............K.
............K.
....K.........
...........KK.
KKKKKKKKKK.KK.
KK..KKKKK.....
T.............
...K.......K..
.........KKKKK

output:

yes

result:

ok single line: 'yes'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 10
.K.K.K.K.T
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
R.K.K.K.K.

output:

no

result:

ok single line: 'no'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4 3
K.T
...
.K.
R..

output:

no

result:

ok single line: 'no'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4 3
..T
...
.K.
R..

output:

yes

result:

ok single line: 'yes'

Test #17:

score: 0
Accepted
time: 80ms
memory: 18516kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #18:

score: 0
Accepted
time: 123ms
memory: 18596kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #19:

score: 0
Accepted
time: 139ms
memory: 30344kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

no

result:

ok single line: 'no'

Test #20:

score: 0
Accepted
time: 142ms
memory: 30344kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

no

result:

ok single line: 'no'

Test #21:

score: 0
Accepted
time: 142ms
memory: 29636kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

yes

result:

ok single line: 'yes'

Test #22:

score: 0
Accepted
time: 137ms
memory: 29948kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #23:

score: 0
Accepted
time: 175ms
memory: 23760kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K....

output:

yes

result:

ok single line: 'yes'

Test #24:

score: 0
Accepted
time: 181ms
memory: 23944kb

input:

750 750
R.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.KKK.K.KKK.K.K.K.K.K.KKK.K.K.K.K....

output:

yes

result:

ok single line: 'yes'

Test #25:

score: 0
Accepted
time: 856ms
memory: 26472kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

no

result:

ok single line: 'no'

Test #26:

score: 0
Accepted
time: 565ms
memory: 26352kb

input:

750 750
R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....

output:

no

result:

ok single line: 'no'

Test #27:

score: 0
Accepted
time: 47ms
memory: 20288kb

input:

744 750
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #28:

score: 0
Accepted
time: 231ms
memory: 25420kb

input:

747 747
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #29:

score: 0
Accepted
time: 409ms
memory: 31140kb

input:

748 748
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #30:

score: 0
Accepted
time: 5452ms
memory: 24956kb

input:

750 750
.......................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #31:

score: 0
Accepted
time: 5744ms
memory: 36580kb

input:

750 750
.....................K........................................................................................................K................................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #32:

score: 0
Accepted
time: 3082ms
memory: 36732kb

input:

750 750
.....................K................................................................................K.......................K.K..............................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #33:

score: 0
Accepted
time: 1216ms
memory: 37816kb

input:

750 750
..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................

output:

yes

result:

ok single line: 'yes'

Test #34:

score: 0
Accepted
time: 5767ms
memory: 36536kb

input:

750 750
.....................K........................................................................................................K................................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #35:

score: 0
Accepted
time: 3116ms
memory: 36820kb

input:

750 750
.....................K................................................................................K.......................K.K..............................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #36:

score: 0
Accepted
time: 1206ms
memory: 37896kb

input:

750 750
..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................

output:

no

result:

ok single line: 'no'

Test #37:

score: 0
Accepted
time: 3482ms
memory: 36648kb

input:

750 750
.......................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #38:

score: 0
Accepted
time: 526ms
memory: 30464kb

input:

750 750
K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................

output:

yes

result:

ok single line: 'yes'

Test #39:

score: 0
Accepted
time: 570ms
memory: 19600kb

input:

750 750
....................................................................................................................................................................................................................................................................................K..................

output:

yes

result:

ok single line: 'yes'

Test #40:

score: 0
Accepted
time: 629ms
memory: 33624kb

input:

750 750
......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................

output:

yes

result:

ok single line: 'yes'

Test #41:

score: 0
Accepted
time: 703ms
memory: 36432kb

input:

750 750
K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................

output:

no

result:

ok single line: 'no'

Test #42:

score: 0
Accepted
time: 5ms
memory: 8636kb

input:

750 750
......K.K..................K......K...K...............K..K............K.........K...............................................................K.....K...............K..K..................................K..K...K..........K....................K.........KKK............................K.K..K.....

output:

no

result:

ok single line: 'no'

Test #43:

score: 0
Accepted
time: 739ms
memory: 36812kb

input:

750 750
......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................

output:

no

result:

ok single line: 'no'

Test #44:

score: 0
Accepted
time: 4125ms
memory: 34096kb

input:

750 750
R..KK..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K.....

output:

yes

result:

ok single line: 'yes'

Test #45:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

6 6
.....T
..K.K.
K.K...
....K.
R..K..
....K.

output:

yes

result:

ok single line: 'yes'

Test #46:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 4
RK..
KK..
...T

output:

yes

result:

ok single line: 'yes'

Test #47:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4 4
.K..
KR..
K...
.K.T

output:

no

result:

ok single line: 'no'