QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749588 | #2924. Lone Rook | zeyu | AC ✓ | 1471ms | 12476kb | C++23 | 4.1kb | 2024-11-15 05:29:43 | 2024-11-15 05:29:43 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;
#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif
const ll mod = 1e9 + 7;
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
bool ingrid(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i ++) cin >> a[i];
int attack[n][m], vis[n][m];
memset(attack, 0, sizeof(attack));
memset(vis, 0, sizeof(vis));
pi s, e;
for (int i = 0; i < n; i ++){
for (int j = 0; j < m; j ++){
if (a[i][j] == 'K'){
for (int k = 0; k < 8; k ++){
int ni = i + dx[k];
int nj = j + dy[k];
if (ingrid(ni, nj)){
attack[ni][nj] ++;
}
}
}
if (a[i][j] == 'R'){
s = {i, j};
}
if (a[i][j] == 'T'){
e = {i, j};
}
}
}
queue<pi> que;
que.push(s);
vis[s.fi][s.se] = 1;
while(! que.empty()){
pi cur = que.front(); que.pop();
int r = cur.fi, c = cur.se;
//cout << r << ' ' << c << '\n';
for (int i = r - 1; i >= 0; i --){
if (a[i][c] == 'K' && attack[i][c] != 0) break;
if (! vis[i][c] && attack[i][c] == 0){
vis[i][c] = 1;
que.push({i, c});
}
}
for (int i = r + 1; i < n; i ++){
if (a[i][c] == 'K' && attack[i][c] != 0) break;
if (! vis[i][c] && attack[i][c] == 0){
vis[i][c] = 1;
que.push({i, c});
}
}
for (int j = c - 1; j >= 0; j --){
if (a[r][j] == 'K' && attack[r][j] != 0) break;
if (! vis[r][j] && attack[r][j] == 0){
vis[r][j] = 1;
que.push({r, j});
}
}
for (int j = c + 1; j < m; j ++){
if (a[r][j] == 'K' && attack[r][j] != 0) break;
if (! vis[r][j] && attack[r][j] == 0){
vis[r][j] = 1;
que.push({r, j});
}
}
if (a[r][c] == 'K'){
a[r][c] = '.';
for (int k = 0; k < 8; k ++){
int nr = r + dx[k];
int nc = c + dy[k];
if (ingrid(nr, nc)){
attack[nr][nc] --;
if (attack[nr][nc] == 0){
bool havevis = false;
for (int i = nr - 1; i >= 0; i --){
if (a[i][nc] == 'K') break;
if (vis[i][nc]) havevis = true;
}
for (int i = nr + 1; i < n; i ++){
if (a[i][nc] == 'K') break;
if (vis[i][nc]) havevis = true;
}
for (int j = nc - 1; j >= 0; j --){
if (a[nr][j] == 'K') break;
if (vis[nr][j]) havevis = true;
}
for (int j = nc + 1; j < m; j ++){
if (a[nr][j] == 'K') break;
if (vis[nr][j]) havevis = true;
}
if (havevis){
vis[nr][nc] = 1;
que.push({nr, nc});
}
}
}
}
}
}
cout << (vis[e.fi][e.se] ? "yes" : "no");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3492kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3828kb
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: 3624kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3552kb
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: 3496kb
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: 3628kb
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: 3596kb
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: 3552kb
input:
4 3 K.T ... .K. R..
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
4 3 ..T ... .K. R..
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 18ms
memory: 6084kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #18:
score: 0
Accepted
time: 23ms
memory: 5800kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #19:
score: 0
Accepted
time: 4ms
memory: 8448kb
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: 4ms
memory: 8520kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 8ms
memory: 8516kb
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: 8ms
memory: 8492kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #23:
score: 0
Accepted
time: 10ms
memory: 8524kb
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: 12ms
memory: 8656kb
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: 37ms
memory: 8812kb
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: 8900kb
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: 7ms
memory: 8764kb
input:
744 750 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #28:
score: 0
Accepted
time: 12ms
memory: 8520kb
input:
747 747 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #29:
score: 0
Accepted
time: 19ms
memory: 8540kb
input:
748 748 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #30:
score: 0
Accepted
time: 1471ms
memory: 12476kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #31:
score: 0
Accepted
time: 392ms
memory: 9144kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #32:
score: 0
Accepted
time: 233ms
memory: 8696kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #33:
score: 0
Accepted
time: 100ms
memory: 8660kb
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: 394ms
memory: 9084kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #35:
score: 0
Accepted
time: 229ms
memory: 8832kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #36:
score: 0
Accepted
time: 95ms
memory: 8844kb
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: 1351ms
memory: 11804kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #38:
score: 0
Accepted
time: 55ms
memory: 8796kb
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: 262ms
memory: 9188kb
input:
750 750 ....................................................................................................................................................................................................................................................................................K..................
output:
yes
result:
ok single line: 'yes'
Test #40:
score: 0
Accepted
time: 56ms
memory: 8592kb
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: 55ms
memory: 8592kb
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: 0ms
memory: 8552kb
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: 53ms
memory: 8656kb
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: 1386ms
memory: 11292kb
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: 3792kb
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: 3488kb
input:
4 4 .K.. KR.. K... .K.T
output:
no
result:
ok single line: 'no'