OpenJudge NOI 2.1 1816:拨钟问题

【题目链接】

OpenJudge NOI 2.1 1816:拨钟问题

【题目考点】

1. 深搜/广搜

2. 枚举

【解题思路】

每个时钟只有4种状态，用4个整数表示这四种状态。根据题意有：0=12点、1=3点、2=6点、3=9点。
设数组t，t[i]表示第i+'A’钟的时间，值只可能是0, 1, 2, 3，那么将该钟移动到下一个时刻的代码为t[i] = (t[i]+1)%4。
因此同样的操作最多执行3次。执行4次移动与不执行，钟表的状态是一样的。
把移动规则保存为一个string类数组mv，设move函数，move(i)表示按照规则i移动钟表。遍历字符串mv[i]，根据字符串中的字母找到钟表，让该钟表变为下一个时刻。

解法1：深搜

深搜函数dfs(int k)表示确定第k种移动的执行次数，搜索到k>9时，每种移动的执行次数就都已经确定了。判断当前各钟是否都是12点（值都为0），如果是，更新最少执行次数，以及执行序列。最后输出执行序列。

解法2：广搜

结点中保存时钟状态和移动序列，初始结点中没有移动。每出队一个结点，在该结点内的移动序列的基础上增加1个移动，并执行该移动改变时钟状态。要增加的移动的编号必须大于等于该结点内移动序列的最后一次移动的编号，而且要保证同一移动的出现次数小于等于3。如果执行移动后，时钟都指向12点（时钟状态值都为0），那么此时的移动序列就是最短的移动序列。用广搜得到的第一个解，就是移动序列最短的解。

解法3：枚举

由于该问题的移动方法数只有9种，每种移动可以移动0, 1, 2, 3次，总移动方案数为$4^9=262144$，可以枚举每种移动方案，选择其中可以使所有钟表为0的，移动次数最少的方案。

【题解代码】

解法1：深搜

#include
using namespace std;
string mv[10] = {"", "ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
int t[9];//t[i]:i+'A'的时间
int sq[50], si;//sq:移动序列 
int min_sq[50], mi = 50;//min_sq:最短移动序列 mi:最少移动次数 
void move(int k)//执行第k种移动 
{
	string s = mv[k];
	for(int i = 0; i < s.length(); ++i)
		t[s[i]-'A'] = (t[s[i]-'A'] + 1) % 4;
}
bool isAllZero()//判断是否所有的时钟都是12点，即t[0]~t[8]都是0 
{
	for(int i = 0; i < 9; ++i)
		if(t[i] != 0)
			return false;
	return true;
}
void dfs(int k)//确定第k种移动进行的次数 
{
	if(k > 9)
	{
		if(isAllZero() && si < mi)
		{
			mi = si;
			memcpy(min_sq, sq, sizeof(sq));	
		}
		return;
	}
	dfs(k+1);
	for(int i = 1; i <= 3; ++i)
	{
		sq[++si] = k;
		move(k);
		dfs(k+1);
	}
	si -= 3;//还原状态 
	move(k);//按照第k规则移动第4次。移动4次后和没移动的状态是一样的，完成还原 
}
int main()
{
	for(int i = 0; i < 9; ++i)
		cin >> t[i];
	dfs(1);
	for(int i = 1; i <= mi; ++i)
		cout << min_sq[i] << ' ';
	return 0; 
}
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

解法2：广搜

#include
using namespace std;
string mv[10] = {"", "ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
struct Node
{
	int t[9];//各钟状态
	vector<int> sq;//已有移动序列 一定是升序序列
	int ln, lct;//ln:序列最后一个数字 lct：序列最后一个数字的个数  
	Node()
	{//都初始化为0 
		memset(t, 0, sizeof(t));
		ln = lct = 0;
	} 
	void move(int k)//执行第k种移动 
	{
		string s = mv[k];
		for(int i = 0; i < s.length(); ++i)
			t[s[i]-'A'] = (t[s[i]-'A'] + 1) % 4;
	}
	bool isAllZero()//判断是否所有的时钟都是12点，即t[0]~t[8]都是0 
	{
		for(int i = 0; i < 9; ++i)
			if(t[i] != 0)
				return false;
		return true;
	}
	void showSq()
	{
		for(int i = 0; i < sq.size(); ++i)
			cout << sq[i] << ' ';
		return;
	} 
};
int main()
{
	Node st;
	for(int i = 0; i < 9; ++i)
		cin >> st.t[i];
	queue<Node> que;
	que.push(st);
	while(que.empty() == false)
	{
		Node u = que.front();
		que.pop();
		if(u.isAllZero())
		{
			u.showSq();
			return 0;
		}
		for(int i = 1; i <= 9; ++i)//执行第i操作 
		{
			if(i > u.ln || i == u.ln && u.lct < 3)//如果i大于u中序列最后一个数，或i等于最后一个数，且最后一个数的个数不超过3个（同一操作最多执行3次） 
			{
				Node d(u);//拷贝构造，d为u的拷贝 
				d.sq.push_back(i);
				d.move(i);//执行第i移动 
				if(i > u.ln)//如果i大于u中序列最后一个数
				{
					d.ln = i;
					d.lct = 1;
				}
				else//i == u.ln
					d.lct++;//u中序列最后一个数的个数加1
				que.push(d);
			} 
		}
	}
	return 0; 
}
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

解法3：枚举

#include
using namespace std;
string mv[10] = {"", "ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
int ori_t[9], t[9];//ori_t[i]:i+'A'的时间 t:临时数组，为ori_t的复制 
int m[10], a[10];//m[i]:第i种移动执行的次数 a[i]:总执行次数最少时，第i种移动执行的次数
void move()//根据m数组执行移动 
{
	for(int i = 1; i <= 9; ++i)
	{
		string s = mv[i];
		for(int j = 1; j <= m[i]; ++j)//第i种移动执行m[i]次 
			for(int k = 0; k < s.length(); ++k)
				t[s[k]-'A'] = (t[s[k]-'A']+1)%4;
	}
}
bool isAllZero()//判断是否所有的时钟都是12点，即t[0]~t[8]都是0 
{
	for(int i = 0; i < 9; ++i)
		if(t[i] != 0)
			return false;
	return true;
}
int sumMoveTimes()//求总移动次数 
{
	int sum = 0;
	for(int i = 1; i <= 9; ++i)
		sum += m[i];
	return sum;
}
int main()
{
	int mn = 50;//最少移动次数 
	for(int i = 0; i < 9; ++i)
		cin >> ori_t[i];
	for(m[1] = 0; m[1] < 4; ++m[1])
	for(m[2] = 0; m[2] < 4; ++m[2])
	for(m[3] = 0; m[3] < 4; ++m[3])
	for(m[4] = 0; m[4] < 4; ++m[4])
	for(m[5] = 0; m[5] < 4; ++m[5])
	for(m[6] = 0; m[6] < 4; ++m[6])
	for(m[7] = 0; m[7] < 4; ++m[7])
	for(m[8] = 0; m[8] < 4; ++m[8])
	for(m[9] = 0; m[9] < 4; ++m[9])
	{
		memcpy(t, ori_t, sizeof(ori_t));
		move();
		if(isAllZero())
		{
			int mt = sumMoveTimes(); 
			if(mt < mn)//如果mt比最少移动次数mn还少 
			{
				mn = mt;
				memcpy(a, m, sizeof(m));//记录各移动的执行次数 
			}
		}
	}
	for(int i = 1; i <= 9; ++i)//根据a数组输出序列 
	{
		while(a[i] > 0)
		{
			cout << i << ' ';
			a[i]--;
		}
	}
	return 0; 
}
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