QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546291#1811. How to Move the Beanssurgutti#WA 7ms32980kbC++171.8kb2024-09-03 22:26:052024-09-03 22:26:05

Judging History

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

  • [2024-09-03 22:26:05]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:32980kb
  • [2024-09-03 22:26:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 1000 + 7;

int h, w;
string s[N];

vector<int> adj[N * N];
int mat[N * N];
int vis[N * N], col = 1;

const int dx[] = {-1, 0, +1, 0};
const int dy[] = {0, -1, 0, +1};

bool dfs(int u) {
	if (vis[u] == col)
		return false;
	vis[u] = col;

	for (int v : adj[u])
		if (mat[v] == -1) {
			mat[v] = u;
			mat[u] = v;
			return true;
		}
	
	for (int v : adj[u])
		if (dfs(mat[v])) {
			mat[v] = u;
			mat[u] = v;
			return true;
		}

	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> h >> w;
	rep(i, h)	cin >> s[i];

	rep(i, h) rep(j, w) {
		mat[i * w + j] = -1;

		if (s[i][j] == '#')
			continue;

		rep(d, 4) {
			int r = i + dx[d];
			int c = (j + dy[d]) % w;

			if (0 <= r && r < h && s[r][c] != '#' && (r != i || c != j)) {
				adj[i * w + j].push_back(r * w + j);
			}
		}
	}

	rep(i, h) rep(j, w) if (mat[i * w + j] == -1) {
		if (!dfs(i * w + j)) {
			col++;
			dfs(i * w + j);
		}
	}

	int won = 0;
	int lost = 0;
	
	rep(i, h) rep(j, w) {
		if (s[i][j] == 'B') {
			int u = i * w + j;
			if (mat[u] == -1) {
				lost++;
			}
			else {
				int v = mat[u];

				mat[u] = -1;
				mat[v] = -1;

				vis[u] = col;
				
				bool fail = false;
				for (int x : adj[u]) {
					if (dfs(x)) {
						fail = true;
						break;
					}
				}

				if (!fail) {
					vis[u] = ++col;
					for (int x : adj[u]) {
						if (dfs(x)) {
							fail = true;
							break;
						}
					}
				}

				if (fail)
					lost++;
				else
					won++;
			}
		}
	}

	// cerr << "won: " << won << '\n';
	// cerr << "lost: " << lost << '\n';

	if (won % 2 == 0)
		cout << "Bob\n";
	else
		cout << "Alice\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 29900kb

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

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

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

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

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

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

input:

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

output:

Bob

result:

ok "Bob"

Test #5:

score: -100
Wrong Answer
time: 7ms
memory: 32980kb

input:

293 249
#B..B..BBB..B.B.B...#BBB..B#B.BBB.#B##B.BB.B.##B#B.BB..B.#B#BB.BB##B#BB#...B..BB..B.B##B.B#B.#.##..B.#..BBBB#.BB..#.BBB#B##BB....B.##B..#...B#..B.BB#B.#...B#.BB.#B#.B...BBB.B.B..B....##.B..B##.BB#B.B.BBB.B#B..#.B.B#.B##..B#.##BB.#BB#.BB.#.B..BB.BB.B
BB.B.#.B#BB.B.B..B.###.B...BB.##.B...B#BB....

output:

Bob

result:

wrong answer 1st words differ - expected: 'Alice', found: 'Bob'