하이퍼 토마토
문제
입력
풀이
구데기 컵 문제에서 몇 안되는 난이도가 매겨진 문제이다.
토마토라는 백준 기본 bfs 문제를 11차원으로 확장한 문제이고, 인덱스를 관리하는게 문제다.
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
80
81
82
83
84
85
86
87
88
89
90
91
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
bool flag = 0;
long long a, b, c, d;
//long long n, m, t, k = 0;
long long ans = 0;
vector<int> val(11, 0);
vector<int> dst;
int sz=1;
for(int i=0;i<11;i++){
cin>>val[i];
dst.push_back(sz);
sz*=val[i];
}
vector<int> vv(sz);
vector<bool> chk(sz, 0);
queue<int> qq;
for(int i=0;i<sz;i++){
cin>>vv[i];
if(vv[i]!=0)chk[i]=1;
if(vv[i]==1){
qq.push(i);
}
}
while(!qq.empty()){
int tmp = qq.front();
chk[tmp]=1;
qq.pop();
for(int i=0;i<11;i++){
if(tmp-dst[i]>=0 && vv[tmp-dst[i]]==0){
flag=0;
for(int j=10;j>i;j--){
if(tmp/dst[j]!=(tmp-dst[i])/dst[j]){
flag=1;
break;
}
}
if(!flag){
vv[tmp-dst[i]]=vv[tmp]+1;
qq.push(tmp-dst[i]);
}
}
if(tmp+dst[i]<sz && vv[tmp+dst[i]]==0){
flag=0;
for(int j=10;j>i;j--){
if(tmp/dst[j]!=(tmp+dst[i])/dst[j]){
flag=1;
break;
}
}
if(!flag){
vv[tmp+dst[i]]=vv[tmp]+1;
qq.push(tmp+dst[i]);
}
}
}
ans = max((int)ans, vv[tmp]);
// for(int i=0;i<4;i++){
// for(int j=0;j<6;j++){
// cout << vv[i*6+j] << ' ';
// }cout<<'\n';
// }
// cout << "----\n";
}
for(int i=0;i<sz;i++){
if(chk[i]==0){
ans=0;
break;
}
}
cout << ans-1;
return 0;
}