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
| #include<iostream>
using namespace std;
const int dr[8]={-2,-2,-1,-1,1,1,2,2};
const int dc[8]={-1,1,-2,2,-2,2,-1,1};
int tb[3][20]={0},n,ct=1,sct,ans[3][20];
struct position{
int r,c;
};
void dfs(position pNow){
for(int i=0;i<8;i++){
position pNext={pNow.r+dr[i],pNow.c+dc[i]};
if(pNext.r>=0 && pNext.c>=0 && pNext.r<3 && pNext.c<n &&
tb[pNext.r][pNext.c]==0){
if(ct<3*n-1){
ct++;
tb[pNext.r][pNext.c]=ct;
dfs(pNext);
ct--;
tb[pNext.r][pNext.c]=0;
}else{
ct++;
tb[pNext.r][pNext.c]=ct;
sct++;
bool lesser=false;
for(int i=0;i<3;i++){
int j;
for(j=0;j<n;j++){
if(ans[i][j]!=tb[i][j]){
lesser=ans[i][j]>tb[i][j];
break;
}
}
if(ans[i][j]!=tb[i][j]){
break;
}
}
if(lesser) for(int i=0;i<3;i++){
for(int j=0;j<n;j++){
ans[i][j]=tb[i][j];
}
}
ct--;
tb[pNext.r][pNext.c]=0;
}
}
}
}
int main(){
cin>>n;
for(int i=0;i<3;i++){
for(int j=0;j<n;j++){
ans[i][j]=10000;
}
}
tb[0][0]=ct;
position pos={0,0};
dfs(pos);
if(sct==0) cout<<"0";
else for(int i=0;i<3;i++){
for(int j=0;j<n;j++){
cout<<ans[i][j]<<" ";
}
}
cout<<"\n";
return 0;
}
|