QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243709 | #6398. Puzzle: Tapa | ucup-team1198# | WA | 1ms | 3628kb | C++20 | 3.0kb | 2023-11-08 16:11:57 | 2023-11-08 16:11:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
char field[100][100];
char ans[100][100];
bool kek[100][100];
const int MAXN = 55 * 55;
vector<int> G[MAXN];
int used[MAXN];
int couple[MAXN];
bool khun(int v, int c) {
if (used[v] == c)
return false;
used[v] = c;
for (int u : G[v]) {
if (couple[u] == -1) {
couple[u] = v;
return true;
}
}
for (int u : G[v]) {
if (khun(couple[u], c)) {
couple[u] = v;
return true;
}
}
return false;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < 2 * n - 1; ++i) {
for (int j = 0; j < 2 * m - 1; ++j) {
cin >> field[i][j];
ans[i][j] = field[i][j];
if (ans[i][j] == '.')
ans[i][j] = '#';
else {
if (ans[i][j] == '2' || ans[i][j] == '4' || ans[i][j] == '7')
kek[i / 2][j / 2] = true;
}
}
}
int left_cnt = 0;
int right_cnt = 0;
auto on_border = [&](int a, int b) {
return a == 0 || a == n - 1 || b == 0 || b == m - 1;
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (kek[i][j]) {
if ((i + j) % 2 == 0)
++left_cnt;
else
++right_cnt;
if (i + 1 < n && kek[i + 1][j] && on_border(i, j) == on_border(i + 1, j)) {
if ((i + j) % 2 == 0)
G[i * m + j].emplace_back((i + 1) * m + j);
else
G[(i + 1) * m + j].emplace_back(i * m + j);
}
if (j + 1 < m && kek[i][j + 1] && on_border(i, j) == on_border(i, j + 1)) {
if ((i + j) % 2 == 0)
G[i * m + j].emplace_back(i * m + j + 1);
else
G[i * m + j + 1].emplace_back(i * m + j);
}
}
}
}
if (left_cnt != right_cnt) {
cout << "NO\n";
return 0;
}
int cnt = 0;
fill(used, used + n * m, -1);
fill(couple, couple + n * m, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if ((i + j) % 2 == 0)
cnt += khun(i * m + j, i * m + j);
}
}
if (cnt == left_cnt) {
for (int i = 0; i < n * m; ++i) {
if (couple[i] != -1) {
int j = couple[i];
int x1 = i / m, y1 = i % m;
int x2 = j / m, y2 = j % m;
ans[x1 + x2][y1 + y2] = '.';
}
}
cout << "YES\n";
for (int i = 0; i < 2 * n - 1; ++i) {
for (int j = 0; j < 2 * m - 1; ++j)
cout << ans[i][j];
cout << '\n';
}
} else {
cout << "NO\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2.4#3 ##### 5#8#5 ##### 3#5#3
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
3 3 3.4.3 ..... 5.7.5 ..... 3.5.3
output:
NO
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
2 2 2.2 ... 2.2
output:
YES 2#2 .#. 2#2
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3368kb
input:
2 50 2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3 ................................................................................................... 2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...
output:
YES 2#4.4#4.4#5#5#5#5#5#5#5#5#4#5#5#4.4#5#5#5#5#4#5#5#5#5#5#4.4#5#4#5#5#5#5#5#5#5#5#5#5#5#4.4#5#5#4#5#3 .#########################.#################.#################.###############################.#### 2#5#5#4.4#5#5#5#4.4#5#5#5#4#5#5#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#5#4.4#5#5#5#5#4#...
result:
wrong answer Clue not satisfied at (1,27), non-consecutive shaded cells