QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#17992#2213. Knightlinmuhan#ML 20ms11676kbC++111.4kb2022-01-15 16:46:492022-05-04 16:36:02

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 16:36:02]
  • 评测
  • 测评结果:ML
  • 用时:20ms
  • 内存:11676kb
  • [2022-01-15 16:46:49]
  • 提交

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;
}

詳細信息

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