QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96479#2924. Lone RookAbdelrahman_KWA 4ms5512kbC++142.6kb2023-04-13 22:01:492023-04-13 22:01:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 22:01:53]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:5512kb
  • [2023-04-13 22:01:49]
  • 提交

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'