QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54156 | #2924. Lone Rook | abdelrahman001 | AC ✓ | 95ms | 8400kb | C++ | 3.1kb | 2022-10-07 09:32:19 | 2022-10-07 09:32:19 |
Judging History
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: 3516kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 3ms
memory: 5616kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 3ms
memory: 5612kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 3ms
memory: 5620kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 3ms
memory: 5624kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5612kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3540kb
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: 3692kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3804kb
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: 3624kb
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: 2ms
memory: 3788kb
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: 3744kb
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: 2ms
memory: 3572kb
input:
4 3 K.T ... .K. R..
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3728kb
input:
4 3 ..T ... .K. R..
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 3ms
memory: 6616kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #18:
score: 0
Accepted
time: 5ms
memory: 6640kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #19:
score: 0
Accepted
time: 15ms
memory: 8004kb
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: 19ms
memory: 8016kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 11ms
memory: 7956kb
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: 18ms
memory: 7940kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #23:
score: 0
Accepted
time: 21ms
memory: 7972kb
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: 18ms
memory: 7996kb
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: 26ms
memory: 8088kb
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: 18ms
memory: 8056kb
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: 11ms
memory: 7928kb
input:
744 750 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #28:
score: 0
Accepted
time: 13ms
memory: 7880kb
input:
747 747 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #29:
score: 0
Accepted
time: 22ms
memory: 8096kb
input:
748 748 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #30:
score: 0
Accepted
time: 18ms
memory: 8400kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #31:
score: 0
Accepted
time: 58ms
memory: 8260kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #32:
score: 0
Accepted
time: 51ms
memory: 8248kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #33:
score: 0
Accepted
time: 46ms
memory: 8004kb
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: 55ms
memory: 8360kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #35:
score: 0
Accepted
time: 55ms
memory: 8248kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #36:
score: 0
Accepted
time: 44ms
memory: 8092kb
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: 95ms
memory: 7928kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #38:
score: 0
Accepted
time: 31ms
memory: 8004kb
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: 24ms
memory: 7996kb
input:
750 750 ....................................................................................................................................................................................................................................................................................K..................
output:
yes
result:
ok single line: 'yes'
Test #40:
score: 0
Accepted
time: 34ms
memory: 7936kb
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: 31ms
memory: 8116kb
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: 7272kb
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: 36ms
memory: 8148kb
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: 87ms
memory: 8012kb
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: 2ms
memory: 3588kb
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: 3752kb
input:
3 4 RK.. KK.. ...T
output:
yes
result:
ok single line: 'yes'
Test #47:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
4 4 .K.. KR.. K... .K.T
output:
no
result:
ok single line: 'no'