QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56315#2924. Lone RookSilverhorse7AC ✓91ms8324kbC++3.1kb2022-10-18 18:18:532022-10-18 18:18:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-18 18:18:55]
  • 评测
  • 测评结果:AC
  • 用时:91ms
  • 内存:8324kb
  • [2022-10-18 18:18:53]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e3 + 5;
int n, m, attacked[N][N];
int dxK[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dyK[] = {2, -2, 2, -2, 1, -1, 1, -1};
int dxR[] = {1, -1, 0, 0};
int dyR[] = {0, 0, 1, -1};
bool valid[N][N];
char a[N][N];
queue<pair<int, int>> q;
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
            if(a[i][j] == 'R') {
                valid[i][j] = true;
                q.push({i, j});
            }
        }
    }
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] != 'K')
                continue;
            for(int k = 0;k < 8;k++) {
                int ni = i + dxK[k];
                int nj = j + dyK[k];
                if(ni >= 0 && ni < n && nj >= 0 && nj < m)
                    attacked[ni][nj]++;
            }
        }
    }
    while(!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        if(a[i][j] == 'T')
            return cout << "yes", 0;
        if(a[i][j] == 'K') {
            for(int k = 0;k < 8;k++) {
                int ni = i + dxK[k];
                int nj = j + dyK[k];
                if(ni >= 0 && ni < n && nj >= 0 && nj < m) {
                    attacked[ni][nj]--;
                    if(attacked[ni][nj] == 0) {
                        bool ok = false;
                        for(int p = 0;p < 4 && !ok;p++) {
                            int x = ni, y = nj;
                            while(1) {
                                x += dxR[p];
                                y += dyR[p];
                                if(x < 0 || x >= n || y < 0 || y >= m)
                                    break;
                                if(valid[x][y]) {
                                    ok = true;
                                    break;
                                }
                                if(a[x][y] == 'K')
                                    break;
                            }
                        }
                        if(ok) {
                            q.push({ni, nj});
                            valid[ni][nj] = true;
                        }
                    }
                }
            }
        }
        for(int k = 0;k < 4;k++) {
            int ni = i, nj = j;
            while(1) {
                ni += dxR[k];
                nj += dyR[k];
                if(ni < 0 || ni >= n || nj < 0 || nj >= m || valid[ni][nj])
                    break;
                if(!attacked[ni][nj]) {
                    q.push({ni, nj});
                    valid[ni][nj] = true;
                }
                if(a[ni][nj] == 'K')
                    break;
            }
        }
    }
    cout << "no";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3688kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3764kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

2 5
RKKK.
...KT

output:

no

result:

ok single line: 'no'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

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

output:

no

result:

ok single line: 'no'

Test #7:

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

input:

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

output:

no

result:

ok single line: 'no'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

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

output:

no

result:

ok single line: 'no'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3724kb

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: 2ms
memory: 3688kb

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: 1ms
memory: 3652kb

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: 2ms
memory: 3608kb

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: 1ms
memory: 3572kb

input:

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

output:

no

result:

ok single line: 'no'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #17:

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

input:

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

output:

yes

result:

ok single line: 'yes'

Test #18:

score: 0
Accepted
time: 8ms
memory: 6584kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #19:

score: 0
Accepted
time: 12ms
memory: 7824kb

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: 13ms
memory: 7940kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

no

result:

ok single line: 'no'

Test #21:

score: 0
Accepted
time: 11ms
memory: 7844kb

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: 12ms
memory: 8032kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #23:

score: 0
Accepted
time: 12ms
memory: 8160kb

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: 16ms
memory: 8076kb

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: 11ms
memory: 8144kb

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: 27ms
memory: 7988kb

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: 22ms
memory: 7988kb

input:

744 750
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #28:

score: 0
Accepted
time: 14ms
memory: 7812kb

input:

747 747
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #29:

score: 0
Accepted
time: 20ms
memory: 8144kb

input:

748 748
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

yes

result:

ok single line: 'yes'

Test #30:

score: 0
Accepted
time: 12ms
memory: 8324kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #31:

score: 0
Accepted
time: 51ms
memory: 8320kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #32:

score: 0
Accepted
time: 52ms
memory: 8076kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #33:

score: 0
Accepted
time: 33ms
memory: 8020kb

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: 52ms
memory: 8204kb

input:

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

output:

no

result:

ok single line: 'no'

Test #35:

score: 0
Accepted
time: 48ms
memory: 8036kb

input:

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

output:

no

result:

ok single line: 'no'

Test #36:

score: 0
Accepted
time: 40ms
memory: 8136kb

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: 91ms
memory: 7852kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #38:

score: 0
Accepted
time: 25ms
memory: 7980kb

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: 18ms
memory: 8004kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #40:

score: 0
Accepted
time: 35ms
memory: 7996kb

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: 33ms
memory: 8072kb

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: 13ms
memory: 7384kb

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: 37ms
memory: 8168kb

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: 86ms
memory: 8008kb

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: 1ms
memory: 3660kb

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: 2ms
memory: 3700kb

input:

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

output:

yes

result:

ok single line: 'yes'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

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

output:

no

result:

ok single line: 'no'