P1213 时钟

admin

https://www.luogu.org/problemnew/show/P1213

题目描述
考虑将如此安排在一个 3 x 3 行列中的九个时钟:



目标要找一个最小的移动顺序将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。

移动方法 受影响的时钟

1 ABDE

2 ABC

3 BCEF

4 ADG

5 BDEFH

6 CFI

7 DEGH

8 GHI

9 EFHI

Example



[但这可能不是正确的方法，请看下面]

输入输出格式
输入格式：
第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。

输出格式：
单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。

如果有多种方案，输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。

输入输出样例
输入样例#1：
9 9 12
6 6 6
6 3 6
输出样例#1：
4 5 8 9
说明
题目翻译来自NOCOW。

USACO Training Section 1.4

黄煦喆

1. #include<iostream>
   
2. #include<set>
   
3. #include<queue>
   
4. using namespace std;
   
5. int n=9,t,l;
   
6. string const goal="000000000";
   
7. string s,p,qq,ans;
   
8. const int v[10][5]={
   
9.     {0,0,0,0,0},
   
10.     {0,1,3,4,0},
    
11.     {0,1,2,0,0},
    
12.     {1,2,4,5,0},
    
13.     {0,3,6,0,0},
    
14.     {1,3,4,5,7},
    
15.     {2,5,8,0,0},
    
16.     {3,4,6,7,0},
    
17.     {6,7,8,0,0},
    
18.     {4,5,7,8,0},},
    
19. ll[10]={0,4,3,4,3,5,3,4,3,4};
    
20. set<string>se;
    
21. struct ha
    
22. {
    
23.     string clock,step;
    
24.     ha(string str,string st):clock(str),step(st) {}
    
25. };
    
26. queue<ha>q;
    
27. string change(string ss,int k)
    
28. {
    
29.     for(int i=0;i<ll[k];i++)ss[v[k][i]]=(ss[v[k][i]]-'0'+1)%4+'0';
    
30.     return ss;
    
31. }
    
32. int main()
    
33. {
    
34.     for(int i=1;i<=n;++i)cin>>t,s+=t/3%4+'0';
    
35.     q.push(ha(s,"")),se.insert(s);
    
36.     while(!q.empty())
    
37.     {
    
38.         string a=q.front().clock,b=q.front().step;
    
39.         if(a==goal)break;
    
40.         else for(int i=1;i<=n;i++)
    
41.         {
    
42.             p=change(a,i),qq=b+char(i+'0');
    
43.             if(!se.count(p))se.insert(p),q.push(ha(p,qq));
    
44.         }
    
45.         q.pop();
    
46.     }
    
47.     ans=q.front().step,l=ans.size();
    
48.     for(int i=0;i<l;i++)cout<<ans[i]<<' ';
    
49.     return 0;
    
50. }
    

复制代码

黄煦喆

黄煦喆 发表于 2018-10-13 22:40

BFS做的，后面4个点TLE了

admin

盲目穷举就可以了  不需要广搜，注意，钟之间的相互关系。