QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639853 | #2924. Lone Rook | enze114514 | TL | 6478ms | 8928kb | C++20 | 3.3kb | 2024-10-13 23:15:48 | 2024-10-13 23:15:48 |
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 dirx[4] = {1, -1, 0, 0};
int 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));
pair<int, int> st;
auto set = [&](int i, int j, int op) -> void{
if(i - 2 >= 0 && j - 1 >= 0) d[i - 2][j - 1] += op;
if(i - 2 >= 0 && j + 1 < m) d[i - 2][j + 1] += op;
if(i - 1 >= 0 && j - 2 >= 0) d[i - 1][j - 2] += op;
if(i - 1 >= 0 && j + 2 < m) d[i - 1][j + 2] += op;
if(i + 1 < n && j - 2 >= 0) d[i + 1][j - 2] += op;
if(i + 1 < n && j + 2 < m) d[i + 1][j + 2] += op;
if(i + 2 < n && j - 1 >= 0) d[i + 2][j - 1] += op;
if(i + 2 < n && j + 1 < m) d[i + 2][j + 1] += op;
};
for(int i = 0; i < n; i++){
string s;
cin >> s;
for(int j = 0; j < m; j++){
c[i][j] = s[j];
if(c[i][j] == 'R'){
st = {i, j};
}
if(c[i][j] == 'K'){
set(i, j, 1);
}
}
}
while(1){
queue<pair<int, int>> q;
q.push(st);
vector<vector<int>> vis(n + 1, vector<int>(m + 1, 0));
vector<pair<int, int>> hr;
vis[st.first][st.second] = 1;
while(!q.empty()){
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
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(c[dx][dy] == 'K'){
if(!d[dx][dy] && !vis[dx][dy]){
vis[dx][dy] = 1;
hr.pb({dx, dy});
break;
}
break;
}
if(d[dx][dy] || vis[dx][dy]){
}
else{
vis[dx][dy] = 1;
if(c[dx][dy] == 'T'){
cout << "yes" << endl;
return;
}
q.push({dx, dy});
}
dx += dirx[i], dy += diry[i];
}
}
}
if(hr.size() == 0){
cout << "no" << endl;
return;
}
else{
for(auto p : hr){
c[p.first][p.second] = '.';
set(p.first, p.second, -1);
}
}
}
}
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: 1ms
memory: 3532kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3676kb
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: 3536kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3584kb
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: 3580kb
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: 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: 0ms
memory: 3632kb
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: 3528kb
input:
4 3 K.T ... .K. R..
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 3 ..T ... .K. R..
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 31ms
memory: 6136kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #18:
score: 0
Accepted
time: 2831ms
memory: 5392kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #19:
score: 0
Accepted
time: 6478ms
memory: 8132kb
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: 5829ms
memory: 8296kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 6255ms
memory: 8220kb
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: 5678ms
memory: 8160kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #23:
score: 0
Accepted
time: 3550ms
memory: 8860kb
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: 3241ms
memory: 8928kb
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: -100
Time Limit Exceeded
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....