QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397211#8114. Labirintlfxxx#0 1ms4320kbC++141.9kb2024-04-23 19:43:372024-07-04 03:37:11

Judging History

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

  • [2024-07-04 03:37:11]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4320kb
  • [2024-04-23 19:43:37]
  • 提交

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';
		cout << d[0].find(id(a, b)) << ' ' << d[0].find(id(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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3608kb

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
55 37
4
1 52 1 64
52 64
4
1 36 1 4
36 4
4
1 68 1 66
68 66
2
1 50 1 80
50 80
4
1 84 1 77
84 77
4
1 99 1 68
99 68
4
1 84 1 56
84 56
4
1 5 1 95
5 95
4
1 38 1 68
38 68
4
1 82 1 3
82 3
4
1 64 1 36
64 36
4
1 61 1 21
61 21
4
1 1 1 4
1 4
2
1 2 1 46
2 46
4
1 55 1 100
55 100
4
1 4 1 83
4 83
4
1 53 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: 4304kb

input:

100 100
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...

output:

99 26 77 30
0 0
0
2 4 11 50
104 0
1
2 35 17 37
0 0
0
84 94 33 100
0 0
0
79 53 9 28
0 0
0
24 84 24 39
0 0
0
69 80 94 57
0 0
0
51 90 23 40
0 0
0
12 99 37 98
0 0
0
77 36 80 77
0 0
0
20 77 55 23
0 0
0
62 95 32 16
0 0
0
36 21 31 25
0 0
0
61 89 61 100
0 0
0
18 81 98 73
0 0
0
94 71 79 60
0 0
0
39 74 92 5
0...

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: 0ms
memory: 4320kb

input:

100 100
PPPPCCCCCCCCCPCCPPCCCPPPCCPPCCCPPPPPCCCCCCCPCCCPCCPPCCCPPCCCPPPCPPPPPPCCPPPCCCPPCCCCCPPPPPPPPCPPCPC
PCPCPCCCCCCCPPPCCPPPPPPCPPPCPCPCCPPPCPCPCCPCCCCCCPPPCCPCCPCPCCPPCPPCCPCCPPPCPPPCPPCPCPPPCPCPPCPCCCC
PCPCCCPPCPPPPCCCCCPCPPCCPPPPPCCCPCPPPPPPPCCPPCCPPCCPCCCCCPPCCCPPCPCPPCCPCPCPCPPPPCCPPPPCCPCP...

output:

18 92 81 83
0 0
0
70 52 94 59
0 0
0
79 1 27 19
0 0
0
33 61 14 66
0 0
0
53 90 46 47
0 0
0
91 50 95 41
0 0
0
40 97 51 62
0 0
0
5 13 85 17
0 0
0
64 30 75 39
0 0
0
81 39 54 88
0 0
0
32 91 40 20
0 0
0
10 50 83 82
0 0
0
13 11 89 37
0 0
0
83 65 74 14
0 0
0
66 47 24 73
0 0
0
6 18 51 95
0 0
0
97 74 29 36
0 0...

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: 0ms
memory: 4288kb

input:

100 100
PZCZZZNPZPZPCCCCPNPZCCZZPPPPNCPZNPZPPNZNCPCNPCNCZZNCCZPZPPPZZZCZCZNPZPNZZZPPZPPZZPCPCZPNNCZZCPCNNNZ
NCZZPPCZNZNNNNNNPPNNCPZCZNNPNCCPZZZCZNPZZZNCCNNZPPCPZNPCPCZCZPZCCPPPCZPZCCPNNNNZZZZCZZNZNZPPZPCNZPC
PCCNZCCZZPZPPNZZNPCCNNZPCNPPZZNCPZNZPCZZPPCCCCNNZZCCNPPZNZNZZZNNNNZZNCNCCCNZPCZCPPZPCPCPZNPP...

output:

64 97 40 1
0 0
0
86 36 47 33
0 0
0
87 54 69 87
0 0
0
60 30 80 96
0 0
0
27 84 93 4
0 0
0
24 51 44 20
0 0
0
32 23 46 48
0 0
0
93 7 34 56
0 0
0
41 96 17 22
0 0
0
38 54 43 58
0 0
0
70 52 38 77
0 0
0
81 22 3 85
0 0
0
85 51 44 16
0 0
0
93 65 60 23
0 0
0
24 26 41 37
0 0
0
25 73 80 75
0 0
0
59 99 10 83
0 0
...

result:

wrong answer 1st lines differ - expected: '3', found: '64 97 40 1'