QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#52802#2213. KnightFamiglistmo#WA 63ms45940kbC++141.4kb2022-10-04 15:10:442022-10-04 15:10:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 15:10:51]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:45940kb
  • [2022-10-04 15:10:44]
  • 提交

answer

#include <bits/stdc++.h>
#define id(x, y) ((x - 1) * m + y)
using namespace std;
const int N = 1005;

int col[N * N], bl[N * N];
vector<int> Edge[N * N];
int n, m, r, c, xa, ya, xb, yb, cnt;
char s[N][N];

void dfs(int u, int c) {
    col[u] = c, bl[u] = cnt;
    for(auto v : Edge[u]) 
        if(!col[v]) dfs(v, 3 - c);
}

signed main() {
    scanf("%d%d%d%d", &n, &m, &r, &c);
    int dx[8] = {r, r, -r, -r, c, c, -c, -c};
    int dy[8] = {c, -c, c, -c, r, -r, r, -r};

    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= m; ++ j)
            if(s[i][j] == 'A') xa = i, ya = j;
            else if(s[i][j] == 'B') xb = i, yb = j;
    }
    
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j) if(s[i][j] != '@')
            for(int k = 0; k < 8; ++ k) {
                int x = i + dx[k], y = j + dy[k];
                if(x < 1 || x > n || y < 1 || y > m || s[x][y] == '@') continue;
                Edge[id(i, j)].push_back(id(x, y));
            }
    for(int i = 1; i <= n * n; ++ i) if(!col[i]) ++ cnt, dfs(i, 1);

    if(Edge[id(xa, ya)].size() == 1 && Edge[id(xa, ya)].front() == id(xb, yb))
        return puts("Bob"), 0;
    if(bl[id(xa, ya)] ^ bl[id(xb, yb)]) return puts("Alice"), 0;
    if(col[id(xa, ya)] ^ col[id(xb, yb)]) return puts("Bob"), 0;
    puts("Alice");
    return 0;
}

Details

Test #1:

score: 0
Wrong Answer
time: 63ms
memory: 45940kb