[Link] https://www.acmicpc.net/problem/17140
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int MAX = 5e5 + 1;
int r, c, k;
int a[100][100];
bool cmp(pair<int, int> p1, pair<int, int> p2) {
if(p1.second == p2.second) return p1.first < p2.first;
return p1.second < p2.second;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c >> k;
r--, c--;
for0(i, 3) for0(j, 3) cin >> a[i][j];
int time = 0, row = 3, col = 3;
map<int, int> cntm;
vector<pair<int, int>> cvec;
while(true) {
if(a[r][c] == k) break;
if(time == 100) {
cout << -1;
return 0;
}
if(row >= col) {
int max_col = 0;
for0(i, row) {
cntm.clear();
cvec.clear();
for0(j, col) { if(a[i][j]) cntm[a[i][j]]++; a[i][j] = 0; }
cvec.resize(cntm.size());
copy(cntm.begin(), cntm.end(), cvec.begin());
sort(cvec.begin(), cvec.end(), cmp);
int ub = min(50, (int)cvec.size());
max_col = max(max_col, ub<<1);
for0(j, ub) {
a[i][j<<1] = cvec[j].first;
a[i][j<<1|1] = cvec[j].second;
}
}
col = max(col, max_col);
} else {
int max_row = 0;
for0(j, col) {
cntm.clear();
cvec.clear();
for0(i, row) { if(a[i][j]) cntm[a[i][j]]++; a[i][j] = 0; }
cvec.resize(cntm.size());
copy(cntm.begin(), cntm.end(), cvec.begin());
sort(cvec.begin(), cvec.end(), cmp);
int ub = min(50, (int)cvec.size());
max_row = max(max_row, ub<<1);
for0(i, ub) {
a[i<<1][j] = cvec[i].first;
a[i<<1|1][j] = cvec[i].second;
}
}
row = max(row, max_row);
}
time++;
}
cout << time;
return 0;
}