Posts Tagged ‘广度优先搜索’

POJ 1945 Power Hungry Cows

Posted in PKU OJ on 五月 18th, 2010 by 纳米 – 2 Comments

2010-05-17，阅读题目，Code
2010-05-18，BFS重写，本地测试，爆数组，AC，改非HASH，AC

解题报告：
本来这道题在推荐列表里面是IDA*的。但是我确实不会写启发函数，然后，随便写了个迭代加深严重超时。还是BFS了吧~
扩展状态，把两个变量(wv0, wv1)作为一个整体，不断扩展扩展，可以得到以下代码1中Line63 – Line69的8组新状态。注意保证wv0 > wv1。这样做会MLE和TLE的。用了一种恶心的方法，假定wv1很小，就给定一个很小的数，大于这个数不扩展就好了。正确性不知道，反正把数据过了。开始我写了个HASH的，还写了个指针的指针，第一次写呢。后来发现用了上面那个技巧连HASH都不用。我还是把2份代码都贴出来了。

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

#include <stdio.h>
 
const int maxn = 20003, maxq = 400003, prime0 = 20011, prime1 = 97;
int n, n2, answer, head, last, q[maxq][3];
struct HASH {
	int wv0, wv1;
	HASH *next;
} *hash[prime0][prime1];
 
int input() {
	scanf("%d", &n);
	return 0;
}
 
bool in_hash(int wv0, int wv1) {
	int p0 = wv0 >= prime0 ? wv0 % prime0 : wv0;
	int p1 = wv1 >= prime1 ? wv1 % prime1 : wv1;
	HASH *t = hash[p0][p1];
	while (t != NULL && (t->wv0 != wv0 || t->wv1 != wv1))
		t = t->next;
	return t != NULL;
}
 
void add_hash(int wv0, int wv1) {
	int p0 = wv0 >= prime0 ? wv0 % prime0 : wv0;
	int p1 = wv1 >= prime1 ? wv1 % prime1 : wv1;
	HASH **t = &hash[p0][p1];
	while (*t != NULL)
		t = &((*t)->next);
	*t = new HASH;
	(*t)->wv0 = wv0, (*t)->wv1 = wv1;
	(*t)->next = NULL;
}
 
bool add_node(int wv0, int wv1, int step) {
	if (wv0 == n || wv1 == n)
		return true;
	if (wv0 < wv1) {
		int temp = wv0;
		wv0 = wv1;
		wv1 = temp;
	}
	if (wv0 == wv1 || wv0 >= n2 || wv1 >= prime1)
		return false;
	if (!in_hash(wv0, wv1)) {
		add_hash(wv0, wv1);
		++last;
		q[last][0] = wv0;
		q[last][1] = wv1;
		q[last][2] = step;
	}
	return false;
}
 
int work() {
	n2 = n << 1;
	head = last = -1;
	add_node(1, 0, 0);
	while (head < last) {
		++head;
		int wv0 = q[head][0], wv1 = q[head][1], step1 = q[head][2] + 1;
		if (	add_node(wv0+wv0, wv1, step1) ||
				add_node(wv0+wv1, wv1, step1) ||
				add_node(wv1+wv1, wv1, step1) ||
				add_node(wv0, wv0+wv0, step1) ||
				add_node(wv0, wv0+wv1, step1) ||
				add_node(wv0, wv1+wv1, step1) ||
				add_node(wv0, wv0-wv1, step1) ||
				add_node(wv0-wv1, wv0, step1)) {
			answer = step1;
			break;
		}
	}
	return 0;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	input();
	work();
	output();
	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
70
71
72

#include <stdio.h>
 
const int maxn = 20003, maxq = 700003, prime0 = 20101, prime1 = 97;
int n, n2, answer, head, last, q[maxq][3];
bool hash[prime0][prime1];
 
int input() {
	scanf("%d", &n);
	return 0;
}
 
bool in_hash(int wv0, int wv1) {
	return hash[wv0][wv1];
}
 
void add_hash(int wv0, int wv1) {
	hash[wv0][wv1] = true;
}
 
bool add_node(int wv0, int wv1, int step) {
	if (wv0 == n || wv1 == n)
		return true;
	if (wv0 < wv1) {
		int temp = wv0;
		wv0 = wv1;
		wv1 = temp;
	}
	if (wv0 == wv1 || wv0 >= n2 || wv1 >= prime1)
		return false;
	if (!in_hash(wv0, wv1)) {
		add_hash(wv0, wv1);
		++last;
		q[last][0] = wv0;
		q[last][1] = wv1;
		q[last][2] = step;
	}
	return false;
}
 
int work() {
	n2 = n + prime1;
	head = last = -1;
	add_node(1, 0, 0);
	while (head < last) {
		++head;
		int wv0 = q[head][0], wv1 = q[head][1], step1 = q[head][2] + 1;
		if (	add_node(wv0+wv0, wv1, step1) ||
				add_node(wv0+wv1, wv1, step1) ||
				add_node(wv1+wv1, wv1, step1) ||
				add_node(wv0, wv0+wv0, step1) ||
				add_node(wv0, wv0+wv1, step1) ||
				add_node(wv0, wv1+wv1, step1) ||
				add_node(wv0, wv0-wv1, step1) ||
				add_node(wv0-wv1, wv0, step1)) {
			answer = step1;
			break;
		}
	}
	return 0;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	input();
	work();
	output();
	return 0;
}

POJ 2286 The Rotation Game

Posted in PKU OJ on 四月 9th, 2010 by 纳米 – Be the first to comment

2010-04-08，阅读题目
2010-04-09，分析题目，实现，一次AC

解题报告：
这题可以采用广度优先搜索解决，关键问题是如何设计状态。
假设中间8个格子的数字已经确定，那么，其余两种数字在这种情况下是等价的。那么，我们把已经确定下来的中间的数字全部置为1，其余均值为0，那么就可以压缩为一个大小范围为0 – 2^24-1的状态。同时，我们可以知道，真正的状态总数为C(8, 24) = 24! / (8! * 16!) = 735471。这样的状态总数完全是可以接受的。
只要中间的数字不能确定，BFS就变得很容易了。但是问题是现在中间的数字并不确定，那么我们只需要枚举中间的数字，分别求出最优值，然后便可求出答案。
但是这样做的效率是低下的，因为，很有可能我按照顺序1、2、3进行广搜，假定中间数字为1、2的时候每次都扩展出70万种状态，而3只需要扩展出100种状态便可到达，显然浪费了很多时间。有一个简单的解决方案，就是在状态的前面增加两位二进制数字，00、01、02分别表示这个状态中间为1、2、3，那么，问题就很好解决了。
我的程序花了58MB内存和2000ms时间。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include <stdio.h>
#include <string.h>
 
const int TARGET = 0x399C0;
const int RE[] = {
	0x3AF77BA, 0x35DEEF5, 0x3FFF80F, 0x3F01FFF, 0x35DEEF5, 0x3AF77BA, 0x3F01FFF, 0x3FFF80F
};
const int RR[][7] = {
	{0,2,6,11,15,20,22},
	{1,3,8,12,17,21,23},
	{4,5,6,7,8,9,10},
	{13,14,15,16,17,18,19},
	{1,3,8,12,17,21,23},
	{0,2,6,11,15,20,22},
	{13,14,15,16,17,18,19},
	{4,5,6,7,8,9,10}
};
const int RL[][7] = {
	{22,0,2,6,11,15,20},
	{23,1,3,8,12,17,21},
	{5,6,7,8,9,10,4},
	{14,15,16,17,18,19,13},
	{3,8,12,17,21,23,1},
	{2,6,11,15,20,22,0},
	{19,13,14,15,16,17,18},
	{10,4,5,6,7,8,9}
};
 
int data[24], statu, q[735473 * 3], pre[735473 * 3], answer_int, answer_step;
short step[735473 * 3];
char o[735473 * 3], answer[1001], ans[1001];
char vis[16777216 * 3] = {0};
 
bool input() {
	scanf("%d", &data[0]);
	if (!data[0])
		return false;
	for (int i = 1; i < 24; ++i)
		scanf("%d", &data[i]);
	return true;
}
 
int operate(int k, int A) {
	int res = A & RE[k];
	for (int i = 0; i < 7; ++i)
		res |= (A >> RR[k][i] & 1) << RL[k][i];
	return res;
}
 
int work_bfs(int arr[]) {
	int head = 0, last = 3;
	for (int i = 1; i <= 3; ++i) {
		q[i] = arr[i];
		o[i] = 0;
		step[i] = 0;
		vis[arr[i]] = statu;
	}
	while (head < last) {
		int A = q[++head];
		int step0 = step[head] + 1;
		if (step0 > answer_step)
			break;
		for (int k = 0; k < 8; ++k) {
			int B = operate(k, A);
			if (vis[B] < statu) {
				if ((B & TARGET) == TARGET)
					answer_step = step0;
				q[++last] = B;
				o[last] = k;
				pre[last] = head;
				step[last] = step0;
				vis[B] = statu;
			}
		}
	}
	return last;
}
 
int work() {
	++statu;
	int arr[4] = {0};
	for (int i = 1; i <= 3; ++i) {
		for (int j = 23; j >= 0; --j)
			arr[i] = (arr[i] << 1) | (data[j] == i ? 1 : 0);
		if ((arr[i] & TARGET) == TARGET) {
			strcpy(answer, "No moves needed");
			answer_int = i;
			return 0;
		}
		arr[i] += (i - 1) * 16777216;
	}
	answer_step = 1000;
	int last = work_bfs(arr);
 
	for (int i = 0; i < 1000; ++i)
		answer[i] = 'Z';
	answer[1000] = '\0';
	for (int i = 1; i <= last; ++i) {
		if ((q[i] & TARGET) == TARGET) {
			int st = i, len = 0;
			while (st > 3) {
				ans[answer_step - ++len] = o[st] + 'A';
				st = pre[st];
			}
			ans[len] = '\0';
			if (strcmp(ans, answer) < 0) {
				strcpy(answer, ans);
				answer_int = q[i] / 16777216 + 1;
			}
		}
	}
	return 0;
}
 
int output() {
	printf("%s\n", answer);
	printf("%d\n", answer_int);
	return 0;
}
 
int main() {
	statu = 0;
	while (input()) {
		work();
		output();
	}
	return 0;
}