题面描述

考虑将如此安排在一个 3×3 行列中的九个时钟:

img

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

移动方法 受影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

Example

img

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

输入格式

输入三行,每行三个正整数,表示一个时钟的初始时间,数字的含意和上面第一个例子一样。

输出格式

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

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

输入输出样例

输入 #1

9 9 12
6 6 6
6 3 6 

输出 #1

4 5 8 9

分析

解法:状态压缩 + 位运算 + BFS
时钟共四个状态。可以使用二进制进行描述。

时间 二进制
12:00 00
3:00 01
6:00 10
9:00 11

一共九个时钟,只需 2×9=182\times9=18个二进制位即可表达。218=2621442^{18}=262144可以用int类型数字存储表达。

以下图为例:

可用二进制位111100101010100110进行表达。

目标状态则是000000000000000000

有若干种方法,求从某一状态到目标状态的最短路径。可用BFS来进行实现。

现在要解决的问题是如何实现某种移动方式。

可发现每种移动方式都是由若干时钟的转动组成,对应二进制变化即:

00 -> 01 -> 10 -> 11 -> 00 …

可发现, 是二进制不断的加1处理。

但是这么处理存在一些问题

  1. 加一过程中存在进位,需要消除进位的影响。(11 + 1 = 100)
  2. 如何单独对18位的二进制中的某些位进行加一处理

这些问题我们放一块解决。

根据之前九个时钟的二进制组成方式,若二进制从右往左,对应低位到高位,最低位为第0位。

则,A对应16、17位,B对应14、15位,…,I对应0、1位。

以旋转A为例,首先取出A对应的2个二进制位,加一实现旋转后,只余下对应的2位二进制,再用这个二进制替换A所对应的二进制位。

具体看过程:

原状态:111100101010100110

取出后:110000000000000000

加一后:000000000000000000

合并后:111100101010100110

若想只取出二进制中某些位的内容,可用&对应位的1来实现。如取出16、17位,可&二进制的11000000000000000000。加一操作通过对应位置加1实现,如A即可与01000000000000000000相加,之后再与11000000000000000000按位与即可保留对应位置的二进制。

共九个时钟,我们可以提前预处理下这些操作数。

A 010000000000000000
110000000000000000
B 000100000000000000
001100000000000000
C 000001000000000000
000011000000000000
D 000000010000000000
000000110000000000
E 000000000100000000
000000001100000000
F 000000000001000000
000000000011000000
G 000000000000010000
000000000000110000
H 000000000000000100
000000000000001100
I 000000000000000001
000000000000000011
int a[9][2];
for(int i=0;i<9;i++){//预处理 对应'A'~'I'
	a[i][0]=(1<<(8-i)*2);
	a[i][1]=3*a[i][0];
}

将’A’ ~ 'I’对应到下标0 ~ 8。某个元素的旋转操作即是:

旋转后=((state&a[e][1])+a[e][0])&a[e][1])

之后再将旋转后的进行替换即可。

state=((旋转后)+(state&(~a[e][1]))

综合一下,对应操作即是:state=(((state&a[e][1])+a[e][0])&a[e][1])+(state&(~a[e][1]))

要注意下符号优先级,不确定就多用括号。

代码实现

详细代码,具体看注释

#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct node{
	int state;//状态
	string s;//最短路径
};
int a[10][2];
//预处理 九种方法
string ways[]={"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
int st[13];
bool vis[270000];

int work(int state,int i){//对时钟进行旋转操作
	int len=ways[i].length();
	for(int j=0;j<len;j++){
		state=(((state&a[ways[i][j]-'A'][1])+a[ways[i][j]-'A'][0])&a[ways[i][j]-'A'][1]) + (state&(~a[ways[i][j]-'A'][1]));
	}
	return state;
}
void bfs(int sta){
	queue <node> q;
	vis[sta]=true;
	q.push(node{sta,""});//存储初始状态
	
	while(!q.empty()){
		node cur=q.front();//取出队首状态
		if(cur.state==0){//判断是否到达目标状态
			for(int i=0;i<(int)cur.s.length();i++){//输出最短路径
				cout<<cur.s[i]<<" ";
			}
			return;	
		}
		q.pop();//不要忘记出队
		for(int i=0;i<9;i++){//遍历 九种操作
			int nxt=work(cur.state,i);//获取操作后的状态
			if(!vis[nxt]){//若未标记该状态
				vis[nxt]=true;//标记状态
				q.push(node{nxt,cur.s+char('0'+i+1)});//入队,并记录最短路径
			}
		}
	}
}

int main(){
	for(int i=0;i<9;i++){//预处理 对应'A' ~ 'I'
		a[i][0]=(1<<(8-i)*2);
		a[i][1]=3*a[i][0];
	}
	//处理 各时钟对应的二进制状态
	st[12]=0;//00
	st[3]=1;//01
	st[6]=2;//10
	st[9]=3;//11
	int x,sta=0;
	for(int i=0;i<9;i++){//输入并拼合九个时钟的二进制
		cin>>x;
		sta+=(st[x]<<((8-i)*2));//形成初始状态
	}
	bfs(sta);
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)