QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639889 | #2924. Lone Rook | enze114514 | TL | 5279ms | 8692kb | C++20 | 3.6kb | 2024-10-13 23:28:27 | 2024-10-13 23:28:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld pi = 3.14159265358979323846;
const int MOD = 998244353;
const ll INF = 1e18;
// Precompute knight moves
const vector<pair<int, int>> knight_moves = {
{-2, -1}, {-2, +1}, {-1, -2}, {-1, +2},
{+1, -2}, {+1, +2}, {+2, -1}, {+2, +1}
};
const int N_MAX = 1e3 + 1; // Adjust based on problem constraints
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> grid(n);
// d[i][j] will store the number of knights threatening cell (i, j)
vector<vector<int>> d(n, vector<int>(m, 0));
pair<int, int> start;
// Function to update the d grid based on knight positions
auto update_knight_threats = [&](int i, int j, int op) {
for (const auto& move : knight_moves) {
int ni = i + move.first;
int nj = j + move.second;
if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
d[ni][nj] += op;
}
}
};
// Read grid and initialize 'd' and start position
for(int i = 0; i < n; i++) {
cin >> grid[i];
for(int j = 0; j < m; j++) {
if(grid[i][j] == 'R') {
start = {i, j};
}
if(grid[i][j] == 'K') {
update_knight_threats(i, j, 1);
}
}
}
// Directions for BFS traversal: up, down, left, right
const vector<pair<int, int>> directions = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
// Initialize visitation grid once
vector<vector<int>> vis(n, vector<int>(m, 0));
int iteration = 1;
while (true) {
queue<pair<int, int>> q;
q.push(start);
// Reset visitation for the new iteration
for(int i = 0; i < n; i++) {
fill(vis[i].begin(), vis[i].end(), 0);
}
vis[start.first][start.second] = 1;
vector<pair<int, int>> removable_knights;
while(!q.empty()) {
pair<int, int> current = q.front(); q.pop();
int x = current.first, y = current.second;
for(const auto& dir : directions) {
int dx = x + dir.first, dy = y + dir.second;
while(dx >= 0 && dy >= 0 && dx < n && dy < m) {
if(grid[dx][dy] == 'K') {
if(d[dx][dy] == 0 && !vis[dx][dy]) {
vis[dx][dy] = 1;
removable_knights.emplace_back(dx, dy);
}
break; // Stop in this direction after encountering a 'K'
}
if(d[dx][dy] > 0 || vis[dx][dy]) {
// If the cell is threatened or already visited, do nothing
}
else {
vis[dx][dy] = 1;
if(grid[dx][dy] == 'T') {
cout << "yes\n";
return 0;
}
q.push({dx, dy});
}
dx += dir.first;
dy += dir.second;
}
}
}
if(removable_knights.empty()) {
cout << "no\n";
return 0;
}
else {
for(auto &[i, j] : removable_knights) {
grid[i][j] = '.'; // Remove the knight
update_knight_threats(i, j, -1); // Update the threat grid
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 3552kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3464kb
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: 3596kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3544kb
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: 3532kb
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: 3564kb
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: 1ms
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: 3596kb
input:
4 3 K.T ... .K. R..
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
4 3 ..T ... .K. R..
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 29ms
memory: 5788kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #18:
score: 0
Accepted
time: 2701ms
memory: 5924kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #19:
score: 0
Accepted
time: 5279ms
memory: 8240kb
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: 5060ms
memory: 8060kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 5132ms
memory: 8188kb
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: 4884ms
memory: 8184kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #23:
score: 0
Accepted
time: 3266ms
memory: 8692kb
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: 3070ms
memory: 8560kb
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....