QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397207#8114. Labirintlfxxx#0 3ms4588kbC++141.8kb2024-04-23 19:41:592024-07-04 03:37:05

Judging History

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

  • [2024-07-04 03:37:05]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:4588kb
  • [2024-04-23 19:41:59]
  • 提交

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 << x << ' ' << y << '\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: 0ms
memory: 3672kb

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:

55 37
4
52 64
4
36 4
4
68 66
2
50 80
4
84 77
4
99 68
4
84 56
4
5 95
4
38 68
4
82 3
4
64 36
4
61 21
4
1 4
2
2 46
4
55 100
4
4 83
4
53 96
4
76 43
4
21 19
1
77 45
4
37 84
4
17 69
4
65 50
4
64 61
3
25 78
4
96 1
4
83 35
4
3 1
2
11 48
4
64 37
4
97 59
4
52 91
4
66 50
4
31 15
4
10 56
4
93 40
4
48 15
4
89 54...

result:

wrong answer 1st lines differ - expected: '4', found: '55 37'

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 2ms
memory: 4588kb

input:

100 100
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...

output:

9826 7630
0
104 1050
1
135 1637
0
8394 3300
0
7853 828
0
2384 2339
0
6880 9357
0
5090 2240
0
1199 3698
0
7636 7977
0
1977 5423
0
6195 3116
0
3521 3025
0
6089 6100
0
1781 9773
0
9371 7860
0
3874 9105
0
9359 844
0
797 3957
0
6981 9139
0
5023 7814
0
4960 7321
0
973 6760
0
9506 2425
0
7349 359
0
8928 53...

result:

wrong answer 1st lines differ - expected: '2', found: '9826 7630'

Subtask #3:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 3ms
memory: 4588kb

input:

100 100
PPPPCCCCCCCCCPCCPPCCCPPPCCPPCCCPPPPPCCCCCCCPCCCPCCPPCCCPPCCCPPPCPPPPPPCCPPPCCCPPCCCCCPPPPPPPPCPPCPC
PCPCPCCCCCCCPPPCCPPPPPPCPPPCPCPCCPPPCPCPCCPCCCCCCPPPCCPCCPCPCCPPCPPCCPCCPPPCPPPCPPCPCPPPCPCPPCPCCCC
PCPCCCPPCPPPPCCCCCPCPPCCPPPPPCCCPCPPPPPPPCCPPCCPPCCPCCCCCPPCCCPPCPCPPCCPCPCPCPPPPCCPPPPCCPCP...

output:

1792 8083
0
6952 9359
0
7801 2619
0
3261 1366
0
5290 4547
0
9050 9441
0
3997 5062
0
413 8417
0
6330 7439
0
8039 5388
0
3191 3920
0
950 8282
0
1211 8837
0
8265 7314
0
6547 2373
0
518 5095
0
9674 2836
0
7625 8035
0
5888 2853
0
3711 8978
0
2369 8471
0
9737 4868
0
9359 3329
0
2786 3886
0
5342 4944
0
917...

result:

wrong answer 1st lines differ - expected: '2', found: '1792 8083'

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 3ms
memory: 4396kb

input:

100 100
PZCZZZNPZPZPCCCCPNPZCCZZPPPPNCPZNPZPPNZNCPCNPCNCZZNCCZPZPPPZZZCZCZNPZPNZZZPPZPPZZPCPCZPNNCZZCPCNNNZ
NCZZPPCZNZNNNNNNPPNNCPZCZNNPNCCPZZZCZNPZZZNCCNNZPPCPZNPCPCZCZPZCCPPPCZPZCCPNNNNZZZZCZZNZNZPPZPCNZPC
PCCNZCCZZPZPPNZZNPCCNNZPCNPPZZNCPZNZPCZZPPCCCCNNZZCCNPPZNZNZZZNNNNZZNCNCCCNZPCZCPPZPCPCPZNPP...

output:

6397 3901
0
8536 4633
0
8654 6887
0
5930 7996
0
2684 9204
0
2351 4320
0
3123 4548
0
9207 3356
0
4096 1622
0
3754 4258
0
6952 3777
0
8022 285
0
8451 4316
0
9265 5923
0
2326 4037
0
2473 7975
0
5899 983
0
2889 1182
0
6971 4089
0
5497 8399
0
604 9358
0
7992 4339
0
5134 8474
0
5046 5992
0
6288 6070
0
560...

result:

wrong answer 1st lines differ - expected: '3', found: '6397 3901'