QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397209 | #8114. Labirint | lfxxx# | 0 | 3ms | 4616kb | C++14 | 1.8kb | 2024-04-23 19:42:45 | 2024-07-04 03:37:06 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 105;
int n, m, a[N][N], b[N][N];
struct dsu {
int fa[N * N];
dsu() {
iota(fa, fa + N, 0);
}
int find(int k)
{
return fa[k] == k ? k : fa[k] = find(fa[k]);
}
void merge(int u, int v)
{
u = find(u), v = find(v);
if (u == v) return;
fa[u] = v;
}
}d[16];
int to(char c)
{
if (c == 'P') return 0;
if (c == 'C') return 1;
if (c == 'Z') return 2;
return 3;
}
int id(int i, int j)
{
return (i - 1) * m + j;
}
bool en;
int main()
{
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n-------------------\n";
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
char c;
cin >> c;
a[i][j] = to(c);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
char c;
cin >> c;
b[i][j] = to(c);
}
}
for (int S = 0; S < 16; ++S) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
if ((S >> a[i][j]) & 1) {
d[S].merge(id(i, j), id(i, j + 1));
}
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
if ((S >> b[i][j]) & 1) {
d[S].merge(id(i, j), id(i + 1, j));
}
}
}
}
int q;
cin >> q;
while (q--) {
int a, b, c, D;
cin >> a >> b >> c >> D;
int x = id(a, b), y = id(c, D), ans = 5;
cout << a << ' ' << b << ' ' << c << ' ' << D << '\n';
for (int S = 0; S < 16; ++S) {
if (d[S].find(x) == d[S].find(y)) {
ans = min(ans, __builtin_popcount(S));
}
}
cout << ans << '\n';
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3632kb
input:
1 100 NPPPZNNPCPCNZNZNZPZZPPPNPCPNPZCPCPCNNCZZPPCPPZPNPNCZCPZNZNPPZNPPZZNPPNCNPZZPZPZZNPCPNNZNNPCNCPZPCNN 100 1 55 1 37 1 52 1 64 1 36 1 4 1 68 1 66 1 50 1 80 1 84 1 77 1 99 1 68 1 84 1 56 1 5 1 95 1 38 1 68 1 82 1 3 1 64 1 36 1 61 1 21 1 1 1 4 1 2 1 46 1 55 1 100 1 4 1 83 1 53 1 96 1 76 1 43 1 21 1...
output:
1 55 1 37 4 1 52 1 64 4 1 36 1 4 4 1 68 1 66 2 1 50 1 80 4 1 84 1 77 4 1 99 1 68 4 1 84 1 56 4 1 5 1 95 4 1 38 1 68 4 1 82 1 3 4 1 64 1 36 4 1 61 1 21 4 1 1 1 4 2 1 2 1 46 4 1 55 1 100 4 1 4 1 83 4 1 53 1 96 4 1 76 1 43 4 1 21 1 19 1 1 77 1 45 4 1 37 1 84 4 1 17 1 69 4 1 65 1 50 4 1 64 1 61 3 1 25 1...
result:
wrong answer 1st lines differ - expected: '4', found: '1 55 1 37'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1ms
memory: 4340kb
input:
100 100 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
99 26 77 30 0 2 4 11 50 1 2 35 17 37 0 84 94 33 100 0 79 53 9 28 0 24 84 24 39 0 69 80 94 57 0 51 90 23 40 0 12 99 37 98 0 77 36 80 77 0 20 77 55 23 0 62 95 32 16 0 36 21 31 25 0 61 89 61 100 0 18 81 98 73 0 94 71 79 60 0 39 74 92 5 0 94 59 9 44 0 8 97 40 57 0 70 81 92 39 0 51 23 79 14 0 50 60 74 21...
result:
wrong answer 1st lines differ - expected: '2', found: '99 26 77 30'
Subtask #3:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 2ms
memory: 4280kb
input:
100 100 PPPPCCCCCCCCCPCCPPCCCPPPCCPPCCCPPPPPCCCCCCCPCCCPCCPPCCCPPCCCPPPCPPPPPPCCPPPCCCPPCCCCCPPPPPPPPCPPCPC PCPCPCCCCCCCPPPCCPPPPPPCPPPCPCPCCPPPCPCPCCPCCCCCCPPPCCPCCPCPCCPPCPPCCPCCPPPCPPPCPPCPCPPPCPCPPCPCCCC PCPCCCPPCPPPPCCCCCPCPPCCPPPPPCCCPCPPPPPPPCCPPCCPPCCPCCCCCPPCCCPPCPCPPCCPCPCPCPPPPCCPPPPCCPCP...
output:
18 92 81 83 0 70 52 94 59 0 79 1 27 19 0 33 61 14 66 0 53 90 46 47 0 91 50 95 41 0 40 97 51 62 0 5 13 85 17 0 64 30 75 39 0 81 39 54 88 0 32 91 40 20 0 10 50 83 82 0 13 11 89 37 0 83 65 74 14 0 66 47 24 73 0 6 18 51 95 0 97 74 29 36 0 77 25 81 35 0 59 88 29 53 0 38 11 90 78 0 24 69 85 71 0 98 37 49 ...
result:
wrong answer 1st lines differ - expected: '2', found: '18 92 81 83'
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 3ms
memory: 4616kb
input:
100 100 PZCZZZNPZPZPCCCCPNPZCCZZPPPPNCPZNPZPPNZNCPCNPCNCZZNCCZPZPPPZZZCZCZNPZPNZZZPPZPPZZPCPCZPNNCZZCPCNNNZ NCZZPPCZNZNNNNNNPPNNCPZCZNNPNCCPZZZCZNPZZZNCCNNZPPCPZNPCPCZCZPZCCPPPCZPZCCPNNNNZZZZCZZNZNZPPZPCNZPC PCCNZCCZZPZPPNZZNPCCNNZPCNPPZZNCPZNZPCZZPPCCCCNNZZCCNPPZNZNZZZNNNNZZNCNCCCNZPCZCPPZPCPCPZNPP...
output:
64 97 40 1 0 86 36 47 33 0 87 54 69 87 0 60 30 80 96 0 27 84 93 4 0 24 51 44 20 0 32 23 46 48 0 93 7 34 56 0 41 96 17 22 0 38 54 43 58 0 70 52 38 77 0 81 22 3 85 0 85 51 44 16 0 93 65 60 23 0 24 26 41 37 0 25 73 80 75 0 59 99 10 83 0 29 89 12 82 0 70 71 41 89 0 55 97 84 99 0 7 4 94 58 0 80 92 44 39 ...
result:
wrong answer 1st lines differ - expected: '3', found: '64 97 40 1'