华师一附中OI组

标题: P1213 时钟 [打印本页]
作者: admin    时间: 2018-7-3 16:23
标题: P1213 时钟
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
作者: 黄煦喆    时间: 2018-10-13 22:40
  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
黄煦喆 发表于 2018-10-13 22:40

BFS做的，后面4个点TLE了
作者: admin    时间: 2018-10-14 08:27
盲目穷举就可以了  不需要广搜，注意，钟之间的相互关系。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2