QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18097#2213. KnightAK_Dream#WA 163ms58904kbC++141.6kb2022-01-16 11:01:442022-05-04 17:04:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:04:29]
  • 评测
  • 测评结果:WA
  • 用时:163ms
  • 内存:58904kb
  • [2022-01-16 11:01:44]
  • 提交

answer

#include <bits/stdc++.h>
#define N 1005
#define pb push_back
using namespace std;

int n, m, R, C, id[N][N], col[N*N];
int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, 1, -1};
char s[N][N];
vector<int> E[N*N];

inline bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m && s[x][y] != '#';
}

void dfs(int x) {
    for (auto y : E[x]) {
        if (col[y] == -1) {
            col[y] = col[x]^1;
            dfs(y);
        }
    }
}

int main() {
    scanf("%d %d %d %d", &n, &m, &R, &C);
    if (!R && !C) {
        puts("Bob"); return 0;
    }
    int tot = 0, A = 0, B = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i]+1);
        for (int j = 1; j <= m; j++) if (s[i][j] != '#') {
            id[i][j] = ++tot;
            if (s[i][j] == 'A') A = tot;
            else if (s[i][j] == 'B') B = tot;
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        for (int d = 0; d < 4; d++) {
            int p = i+dx[d]*R, q = j+dy[d]*C;
            if (ok(p, q)) E[id[i][j]].pb(id[p][q]);
        }
        for (int d = 0; d < 4; d++) {
            int p = i+dx[d]*C, q = j+dy[d]*R;
            if (ok(p, q)) E[id[i][j]].pb(id[p][q]);
        }
    }
    memset(col, -1, sizeof(col));
    int now = 0;
    for (int i = 1; i <= tot; i++) if (col[i] == -1) {
        col[i] = now; dfs(i); now += 2;
    }
    bool flg = 1;
    for (auto y : E[A]) if (y != B) flg = 0;
    if (flg) puts("Bob");
    else if (col[A]/2 != col[B]/2) puts("Alice");
    else if (col[A] == col[B]) puts("Alice");
    else puts("Bob"); 
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 59ms
memory: 49208kb

Test #2:

score: 0
Accepted
time: 10ms
memory: 32548kb

Test #3:

score: 0
Accepted
time: 149ms
memory: 55200kb

Test #4:

score: 0
Accepted
time: 163ms
memory: 58904kb

Test #5:

score: 0
Accepted
time: 4ms
memory: 31316kb

Test #6:

score: 0
Accepted
time: 22ms
memory: 37100kb

Test #7:

score: -100
Wrong Answer
time: 8ms
memory: 32060kb