QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#640100 | #2924. Lone Rook | enze114514 | AC ✓ | 5767ms | 37896kb | C++20 | 4.3kb | 2024-10-14 04:58:27 | 2024-10-14 04:58:27 |
Judging History
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;
}
詳細信息
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'