하이퍼 토마토
문제
입력
풀이
구데기 컵 문제에서 몇 안되는 난이도가 매겨진 문제이다.
토마토라는 백준 기본 bfs 문제를 11차원으로 확장한 문제이고, 인덱스를 관리하는게 문제다.
n차원 배열도 컴퓨터 내부적으로 보면 1차원 배열과 똑같다는 것을 떠올려서 풀이를 했고
11개의 변수에 대해 앞에서부터 곱하면 그것이 차원을 나누는 기준이 되어 dst 배열에 저장했다.
그 다음 다른 bfs 문제처럼 0, 1, -1에 대한 처리를 한 후 퍼져나가는 것을 구현해야 하는데
1
2
if(tmp-dst[i]>=0 && vv[tmp-dst[i]]==0)
if(tmp+dst[i]>=0 && vv[tmp+dst[i]]==0)
로 각각 확인을 하면 된다.
그런데 tmp가 i번째 차원에 있을 때 dst[i]를 더하거나 뺐을 때 i번째 차원의 다른 덩어리로 이동할 수가 있다.
1
2
3
4
5
6
7
8
if(tmp/dst[j]!=(tmp-dst[i])/dst[j]){
flag=1;
break;
}
if(tmp/dst[j]!=(tmp-dst[i])/dst[j]){
flag=1;
break;
}
그렇기에 위의 코드로 다른 덩어리로 넘어질 때의 예외 처리를 해줬다.
1차원 배열로 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;
}