首页 > USACO题解 > USACO The Clocks|BFS

USACO The Clocks|BFS

The Clocks一题看完之后第一个想到的就是BFS(其实很有多方法可以解决,有兴趣可以去参考参考NOCOW的解题代码)。对于这样的BFS,我都是定义结构体来作为节点,像本题中使用一个state字符串来记录当前的状态,然后最开始用了一个vector来记录已经出现过的状态,结果在提交的时候悲剧的TLE了。

于是各种加优化,想了想,中间产生大量状态,然后每次都从头到尾的搜索vector效率是低了点(对于vector来说,全局的find函数是O(N)的复杂度),于是改用map,map排序了,复杂度O(lgN),但是还是TLE了,虽然过了第三组数据,但是第四组TLE。

最后,我不得不参考了NOCOW的解题代码,首先,BFS也是可以剪枝的,因为如果某一种变换使用了4次,则相当于没有使用(3->6->9->12->3),而四次以上的,则都在前三次出现了,所以每一种变换最多使用3次。其次,我们还可以使用hash来判重。3-6-9-12可以改写成四进制的0-1-2-3,hash数组就开到4^9左右。接下来就顺利的通过了。下面是我的代码(比较乱)另外,我个人认为string这个东东很耗时间,能不用则不用。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
	ID:stackex1
	LANG:C++
	PROG:clocks
*/
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
 
struct Node
{
public:
	int h[9];
	vector<int> path;
	int cnt[10];
};
 
int hash(int a[])
{
	int res = 0, i;
	for(i = 0; i < 9; ++i)
		res = res*4 + a[i]/3 - 1;
	return res;
}
 
Node start;
char step[10][10] = {"@_@!", "ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
bool v[300000] = {0};
int cnt[10] = {0};
int f_s[] = {12, 12, 12, 12, 12, 12, 12, 12, 12};
int finalstate = hash(f_s);
 
void BFS(Node start)
{
	FILE *fout = fopen("clocks.out", "w");
	queue<Node> q;
	Node t, tmp;
	int j, k, len, t_state;
	q.push(start);
	v[hash(start.h)] = true;
 
	while(!q.empty())
	{
		t = q.front();
		q.pop();
		for(j = 1; j <= 9; ++j)
		{
			tmp = t;
			if(tmp.cnt[j] == 3)continue;
			++tmp.cnt[j];
			len = strlen(step[j]);
			for(k = 0; k < len; ++k)
			{
				if(tmp.h[step[j][k]-'A'] != 12)
					tmp.h[step[j][k]-'A'] += 3;
				else
					tmp.h[step[j][k]-'A'] = 3;
			}
			tmp.path.push_back(j);
			t_state = hash(tmp.h);
			if(!v[t_state])
			{
				q.push(tmp);
				v[t_state] = true;
				if(t_state == finalstate)
				{
					vector<int>::iterator iter = tmp.path.begin();
					fprintf(fout, "%d", *iter);
					for(++iter; iter != tmp.path.end(); ++iter)
					{
						fprintf(fout, " %d", *iter);
					}
					fprintf(fout, "\n");
					fclose(fout);
					return ;
				}
			}
		}
	}
}
 
int main(int argc, char **argv)
{
	FILE *fin = fopen("clocks.in", "r");
 
	int i, n = 9;
	for(i = 0; i < n; ++i)
	{
		fscanf(fin, "%d", &start.h[i]);
	}
	BFS(start);
 
	fclose(fin);
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO The Clocks|BFS
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: , , , , ,
  1. 星宇
    2013年2月6日10:44 | #1

    我写了和你的思路一样的代码放上去,仍旧超时T_T,超了0.091秒,case 6

    [回复]

  2. 星宇
    2013年2月6日10:50 | #2

    [em001]

    [回复]

    代码疯子 回复:

    @星宇, 额 可能我的代码本来就耗时

    [回复]