QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#18090#2213. KnightAK_Dream#WA 156ms58896kbC++141.5kb2022-01-16 10:54:422022-05-04 17:04:01

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:01]
  • 评测
  • 测评结果:WA
  • 用时:156ms
  • 内存:58896kb
  • [2022-01-16 10:54:42]
  • 提交

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);
    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;
    }
    if (!E[A].size() || (E[A].size() == 1 && E[A][0] == B)) 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 60ms
memory: 49196kb

Test #2:

score: 0
Accepted
time: 3ms
memory: 32468kb

Test #3:

score: 0
Accepted
time: 156ms
memory: 55128kb

Test #4:

score: 0
Accepted
time: 150ms
memory: 58896kb

Test #5:

score: 0
Accepted
time: 2ms
memory: 31584kb

Test #6:

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

Test #7:

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