【题解】时钟

2022-08-30 19:30:23 浏览数 (1)

题面描述

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

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

移动方法

受影响的时钟

1

ABDE

2

ABC

3

BCEF

4

ADG

5

BDEFH

6

CFI

7

DEGH

8

GHI

9

EFHI

Example

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

输入格式

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

输出格式

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

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

输入输出样例

输入 #1

代码语言：javascript复制
9 9 12
6 6 6
6 3 6

输出 #1

代码语言：javascript复制
4 5 8 9

分析

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

时间

二进制

12：00

00

3：00

01

6：00

10

9：00

11

一共九个时钟，只需 2×9=18个二进制位即可表达。

可以用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

代码语言：javascript复制
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]))

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

代码实现

详细代码，具体看注释

代码语言：javascript复制
#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.

state 二进制

0 人点赞