QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397209#8114. Labirintlfxxx#0 3ms4616kbC++141.8kb2024-04-23 19:42:452024-07-04 03:37:06

Judging History

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

  • [2024-07-04 03:37:06]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:4616kb
  • [2024-04-23 19:42:45]
  • 提交

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'