QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96479 | #2924. Lone Rook | Abdelrahman_K | WA | 4ms | 5512kb | C++14 | 2.6kb | 2023-04-13 22:01:49 | 2023-04-13 22:01:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
const int N = 2e7 + 2;
int dx[] = {-2, -2, 2, 2, 1, 1, -1, -1};
int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};
char arr[755][755];
int freq[755][755], n, m;
bool vis[755][755];
pair<int, int> target, rock;
queue<pair<int, int>> q;
bool valid(int i, int j){
return (i >= 0 && j >= 0 && i < n && j < m);
}
int sign(int x){
if(x < 0)
return -1;
else
return 1;
}
void moveDir(int r, int c, int r1, int c1, int r2, int c2){
for(int i = r1; i != r2; i += sign(r2 - r1)){
for(int j = c1; j != c2; j += sign(c2 - c1)){
if(vis[i][j])
continue;
if(!vis[i][j] && !freq[i][j]){
vis[i][j] = true;
q.push({i, j});
if(arr[i][j] == 'K'){
// q.push({r, c});
for(int k = 0; k < 8; k++){
int ii = i + dx[k];
int jj = j + dy[k];
if(valid(ii, jj)){
freq[ii][jj]--;
arr[ii][jj] = '.';
}
if(ii == rock.first || jj == rock.second)
q.push(rock);
}
return;
}
}
if(arr[i][j] == 'K')
return;
}
}
}
int main() {
cin>>n>>m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>arr[i][j];
if(arr[i][j] == 'R')
rock = {i, j};
if(arr[i][j] == 'T')
target = {i, j};
if(arr[i][j] == 'K'){
for(int x = 0; x < 8; x++){
int ii = i + dx[x];
int jj = j + dy[x];
if(valid(ii, jj))
freq[ii][jj]++;
}
}
}
}
q.push(rock);
vis[rock.first][rock.second] = true;
while(q.size()){
pair<int, int> p = q.front();
q.pop();
if(p == target){
return cout<<"yes", 0;
}
int x = p.first, y = p.second;
// move right
moveDir(x, y, x, y + 1, x + 1, m);
// mve left
moveDir(x, y, x, y - 1, x + 1, -1);
// move up
moveDir(x, y, x - 1, y, -1, y + 1);
// move down
moveDir(x, y, x + 1, y, n, y + 1);
}
cout<<"no";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3420kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3336kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5448kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5460kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5384kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5512kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 4ms
memory: 5440kb
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: 5468kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3408kb
input:
14 6 T.K..K ...... K....K KKK.KK KKK.KK ...... ...... ..K.KK .K...K ...... ..KK.K ...K.. ...... R.K.K.
output:
no
result:
wrong answer 1st lines differ - expected: 'yes', found: 'no'