Problem’s Website
- 时钟
Solution
- 一道比较好的dfs，我们直接对3、6、9、12取模，把9种变化方式用数组存起来，用一个数组存变化的方式，因为是从1-9dfs，所以可以保证输出顺序是字典序最小的。
Code
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
using namespace std;
int sc() {
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-1; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
int node[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}
};
int a[11],now[11],num[11];
namespace Dy {
void dfs(int way) {
for(int i=1; i<=9; i++)
now[i]=a[i];
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++) {
now[i]=now[i]+node[j][i]*num[j];
if(now[i]>5) now[i]-=4;
// cout<<now[i]<<" ";
}
// cout<<endl;
bool flag=0;
for(int i=1; i<=9; i++)
if(now[i]!=4) {
flag=1; break;
}
if(!flag) {
for(int i=1; i<=9; i++)
for(int j=1; j<=num[i]; j++)
printf("%d ",i);
// cout<<endl;
way=10;
return ;
}
if(way==10) return ;
for(int i=0; i<=3; i++)
num[way]=i,dfs(way+1);
}
void RPpp() {
// cout<<node[1][3]<<endl;
for(int i=1; i<=9; i++) {
int x=sc();
a[i]=x/3;
}
dfs(1);
}
};
int main() {
Dy::RPpp();
return 0;
}
rp++