QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#17992 | #2213. Knight | linmuhan# | ML | 20ms | 11676kb | C++11 | 1.4kb | 2022-01-15 16:46:49 | 2022-05-04 16:36:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1100;
int s[N][N], xA, yA, xB, yB, n, m, r, c, cnt;
const int fx[4][2] = {{1, 1}, {-1, 1}, {-1, -1}, {1, -1}};
int colA[N][N];
char tmp;
struct node {
int x, y, col;
};
queue <node> q;
bool vis[N][N];
bool valid (int xx, int yy) {
return (xx >= 1 && xx <= n && yy >= 1 && yy <= m && ! vis[xx][yy] && s[xx][yy]);
}
void bfs (int sx, int sy, int col) {
q.push ((node) {sx, sy, col});
while (! q.empty ()) {
cnt ++;
node now = q.front (); q.pop ();
colA[now.x][now.y] = now.col;
vis[now.x][now.y] = 1;
for (int i=0;i<4;i++) {
int xx = now.x + fx[i][0] * r, yy = now.y + fx[i][1] * c;
if (valid (xx, yy)) {
q.push ((node) {xx, yy, (now.col ^ 1)});
}
}
for (int i=0;i<4;i++) {
int xx = now.x + fx[i][0] * c, yy = now.y + fx[i][1] * r;
if (valid (xx, yy)) {
q.push ((node) {xx, yy, (now.col ^ 1)});
}
}
}
}
int main () {
cin >> n >> m >> r >> c;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin >> tmp;
if (tmp == 'A') s[i][j] = 1, xA = i, yA = j;
if (tmp == 'B') s[i][j] = 1, xB = i, yB = j;
if (tmp == '@') s[i][j] = 0;
if (tmp == '.') s[i][j] = 1;
}
}
bfs (xA, yA, 8); // 8 9
if (cnt <= 1) {
puts ("Bob");
return 0;
}
if (! colA[xB][yB]) {
puts ("Alice");
return 0;
}
if (colA[xB][yB] == 8) {
puts ("Alice");
return 0;
}
puts ("Bob");
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 20ms
memory: 11676kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 5536kb
Test #3:
score: -100
Memory Limit Exceeded