问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2531思路:
更像是枚举的搜索，外加一个简单的对称性减枝，不过耗时比较久
代码:
1 #define MAX_NUM 21
2 int matrix[MAX_NUM][MAX_NUM];
3 int mark[MAX_NUM], mark_num;
4 int num, max;
5
6 int
7 calculate()
8 {
9 int i, j;
10 int sum = 0;
11 for(i=0; i<num; i++)
12 if(mark[i]) {
13 for(j=0; j<num; j++)
14 if(!mark[j])
15 sum += matrix[i][j];
16 }
17 return sum;
18 }
19
20 void
21 dfs(int depth)
22 {
23 int rt;
24 if(depth == num) {
25 rt = calculate();
26 max = rt>max ? rt : max;
27 return;
28 }
29 ++mark_num;
30 mark[depth] = 1; /* mark[depth]=1, put 'depth' into the category I */
31 if(mark_num <= (num>>1)) /* pruning */
32 dfs(depth+1);
33 --mark_num;
34 mark[depth] = 0;
35 dfs(depth+1); /* put 'depth' into the category II */
36 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1606http://acm.pku.edu.cn/JudgeOnline/problem?id=3414思路:
典型的BFS
好玩的就是如何来处理输出，每个状态包含一个指向前一个状态的指针
代码:
1 #define QUEUE_LEN 10000
2 #define MAX_VOL 101
3 const char ops[][12] = {
4 "FILL(1)",
5 "FILL(2)",
6 "DROP(1)",
7 "DROP(2)",
8 "POUR(1,2)",
9 "POUR(2,1)" };
10 int vola, volb, target;
11 int head, tail;
12 int visited[MAX_VOL][MAX_VOL];
13 struct EACH {
14 int a, b;
15 int opnum;
16 int opidx;
17 struct EACH *pre;
18 } queue[QUEUE_LEN];
19
20 #define ADD(na, nb, num, idx) ++tail; \
21 queue[tail].a = na; \
22 queue[tail].b = nb; \
23 queue[tail].opnum = num+1; \
24 queue[tail].opidx = idx; \
25 queue[tail].pre = queue+head; \
26 visited[na][nb] = 1;
27
28 void
29 output(struct EACH *item)
30 {
31 if(item == NULL)
32 return;
33 output(item->pre);
34 if(item->opidx >= 0)
35 printf("%s\n", ops[item->opidx]);
36 }
37
38 void
39 bfs()
40 {
41 int cur_a, cur_b, ta, tb, cur_opnum;
42 queue[tail].a = 0;
43 queue[tail].b = 0;
44 queue[tail].opnum = 0;
45 queue[tail].opidx = -1;
46 queue[tail].pre = NULL;
47 visited[0][0] = 1;
48 while(head < tail) {
49 ++head;
50 cur_a = queue[head].a;
51 cur_b = queue[head].b;
52 cur_opnum = queue[head].opnum;
53 if(cur_a==target || cur_b==target) {
54 printf("%d\n", cur_opnum);
55 output(queue+head);
56 return;
57 }
58 if(!visited[vola][cur_b]) { /* FILL(1) */
59 ADD(vola, cur_b, cur_opnum, 0);
60 }
61 if(!visited[cur_a][volb]) { /* FILL(2) */
62 ADD(cur_a, volb, cur_opnum, 1);
63 }
64 if(!visited[0][cur_b]) { /* DROP(1) */
65 ADD(0, cur_b, cur_opnum, 2);
66 }
67 if(!visited[cur_a][0]) { /* DROP(2) */
68 ADD(cur_a, 0, cur_opnum, 3);
69 }
70 /* POUR(1,2) */
71 if(cur_a+cur_b > volb) {
72 ta = cur_a+cur_b-volb;
73 tb = volb;
74 if(!visited[ta][tb]) {
75 ADD(ta, tb, cur_opnum, 4);
76 }
77 } else {
78 ta = 0;
79 tb = cur_a + cur_b;
80 if(!visited[ta][tb]) {
81 ADD(ta, tb, cur_opnum, 4);
82 }
83 }
84 /* POUR(2,1) */
85 if(cur_a+cur_b > vola) {
86 ta = vola;
87 tb = cur_a+cur_b-vola;
88 if(!visited[ta][tb]) {
89 ADD(ta, tb, cur_opnum, 5);
90 }
91 } else {
92 ta = cur_a + cur_b;
93 tb = 0;
94 if(!visited[ta][tb]) {
95 ADD(ta, tb, cur_opnum, 5);
96 }
97 }
98 }
99 printf("impossible\n");
100 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3083思路:
对于求最短路径，BFS即可解决，没有什么难度
该题的难点在于如何求沿左、沿右走的问题
刚开始，完全不知道这是什么意思，无奈只能在网上看代码，总结如下:
沿左策略的一般次序: left, up, right, down
沿右策略的一般次序: right, up, left, down
求解的关键是如何根据前一个方向以及一般次序来决定目前访问上下左右四个方向的顺序，例如:
对于沿左前进策略，如果前一个方向是right，那么访问次序是up, right, down, left(与前一个方向相反的方向总是放在最后)
代码:
1 #define MAX_LEN 42
2 #define QUEUE_LEN 1600
3 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
4 char maze[MAX_LEN][MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col;
7 int start_x, start_y;
8 /* left, up, right, down */
9 const int dx[] = {0, -1, 0, 1};
10 const int dy[] = {-1, 0, 1, 0};
11 /* right, up, left, down */
12 const int dx_right[] = {0, -1, 0, 1};
13 const int dy_right[] = {1, 0, -1, 0};
14 int lcount, rcount;
15 int head, tail;
16 struct EACH {
17 int x, y;
18 int mv;
19 } queue[QUEUE_LEN];
20
21
22 void
23 init()
24 {
25 int i;
26 char *p;
27 memset(visited, 0, sizeof(visited));
28 head = -1;
29 tail = 0;
30 lcount = rcount = 0;
31 scanf("%d %d", &col, &row);
32 for(i=0; i<row; i++) {
33 scanf("%s", maze[i]);
34 if((p=strchr(maze[i], 'S')) != NULL) {
35 start_x = i;
36 start_y = p-maze[i];
37 }
38 }
39 }
40
41 /*
42 * dir: previous direction
43 * switch(dir):
44 * case(right): up right down left (order)
45 * case(up): left up right down
46 * case(left): down left up right
47 * case(down): right down left up
48 */
49 void
50 dfs_left(int x, int y, int dir)
51 {
52 int i, tx, ty;
53 ++lcount;
54 if(maze[x][y] == 'E') {
55 return;
56 }
57 dir = (dir+3)%4;
58 for(i=0; i<4; i++) {
59 tx = x + dx[(dir+i)%4];
60 ty = y + dy[(dir+i)%4];
61 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
62 dfs_left(tx, ty, (dir+i)%4);
63 break;
64 }
65 }
66 }
67
68 void
69 dfs_right(int x, int y, int dir)
70 {
71 int i, tx, ty;
72 ++rcount;
73 if(maze[x][y] == 'E')
74 return;
75 dir = (dir+3)%4;
76 for(i=0; i<4; i++) {
77 tx = x + dx_right[(dir+i)%4];
78 ty = y + dy_right[(dir+i)%4];
79 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
80 dfs_right(tx, ty, (dir+i)%4);
81 break;
82 }
83 }
84 }
85
86 int
87 bfs()
88 {
89 int i, cx, cy, tx, ty, cmv;
90 memset(visited, 0, sizeof(visited));
91 queue[tail].x = start_x;
92 queue[tail].y = start_y;
93 queue[tail].mv = 1;
94 visited[start_x][start_y] = 1;
95 while(head < tail) {
96 ++head;
97 cx = queue[head].x;
98 cy = queue[head].y;
99 cmv = queue[head].mv;
100 if(maze[cx][cy] == 'E')
101 return cmv;
102 for(i=0; i<4; i++) {
103 tx = cx + dx[i];
104 ty = cy + dy[i];
105 if(is_valid(tx, ty) && !visited[tx][ty] && maze[tx][ty]!='#') {
106 ++tail;
107 queue[tail].x = tx;
108 queue[tail].y = ty;
109 queue[tail].mv = cmv+1;
110 visited[tx][ty] = 1;
111 }
112 }
113 }
114 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3009思路:
这题要求进行一个简单的游戏，判断最优步数。通常来说，这种判断最短步骤的问题可以使用广度优先搜索解决(bfs),由于题目中地图会由于游戏的进行发生变化，使用bfs会比较麻烦（需要记录地图状态），注意到题目中有一个条件：只能在10步以内完成游戏，于是我们可以考虑使用深度优先搜索（dfs）+限制步数来完成。简单的说：就是我们遍历整个搜索树寻找可能解中的最优步数，但当搜索树深度大于10时则不必继续搜索下去。
代码:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 #define INF 100000
3 #define THROW_MAX 10
4 #define MAX_LEN 21
5 int row, col, start_x, start_y;
6 int board[MAX_LEN][MAX_LEN];
7 int min;
8 const int dx[] = {0, 0, -1, 1};
9 const int dy[] = {-1, 1, 0, 0};
10
11 void
12 dfs(int depth, int x, int y)
13 {
14 int i, tx, ty;
15 if(depth>=THROW_MAX || depth>=min) /* pruning */
16 return;
17 for(i=0; i<4; i++) {
18 tx = x;
19 ty = y;
20 if(board[tx+dx[i]][ty+dy[i]] == 1) /* block immediately */
21 continue;
22 do {
23 tx += dx[i];
24 ty += dy[i];
25 if(is_valid(tx, ty) && board[tx][ty] == 3) { /* end */
26 min = depth+1;
27 return;
28 }
29 } while(is_valid(tx, ty) && board[tx][ty]!=1);
30 if(is_valid(tx, ty)) {
31 board[tx][ty] = 0; /* the block disappears */
32 dfs(depth+1, tx-dx[i], ty-dy[i]);
33 board[tx][ty] = 1;
34 }
35 }
36 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2488思路:
十分熟悉的DFS
需要注意的一点是: 字典序，所以八个方向的搜索次序不是任意的，从左向右，从上到下，这里定义:
1 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
2 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
另外，我觉得只有从任何一个点出发都没法遍历，才应该输出impossible
不过，看了网上的代码，都只需要从左上角出发即可得出结论
代码:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 struct Item {
3 int x, y;
4 } path[MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col, flag;
7 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
8 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
9
10 void
11 dfs(int depth, int x, int y)
12 {
13 int i, tx, ty;
14 visited[x][y] = 1;
15 path[depth].x = x;
16 path[depth].y = y;
17 if(depth+1 == row*col) {
18 if(!flag) {
19 flag = 1;
20 for(i=0; i<row*col; i++)
21 printf("%c%d", 'A'+path[i].y, path[i].x+1);
22 printf("\n");
23 }
24 }
25 if(!flag) {
26 for(i=0; i<8; i++) {
27 tx = x + dx[i];
28 ty = y + dy[i];
29 if(is_valid(tx, ty) && !visited[tx][ty])
30 dfs(depth+1, tx, ty);
31 }
32 }
33 visited[x][y] = 0;
34 }
35
36 void
37 solve()
38 {
39 int i, j;
40 memset(visited, 0, sizeof(visited));
41 flag = 0;
42 for(i=0; i<row; i++)
43 for(j=0; j<col; j++)
44 if(!flag)
45 dfs(0, i, j);
46 if(!flag)
47 printf("impossible\n");
48 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2251思路:
三维的迷宫
其实，该题是典型的BFS
不过由于二维迷宫的影响以及网上题目分类的误导，开始直接DFS，结果TLE
值得小庆祝一番的是: 这是AC的第50题(*^__^*) 嘻嘻……，继续加油
代码:
TLE的DFS
1 void
2 dfs(int sl, int sr, int sc, int m)
3 {
4 if(m >= min) /* pruning */
5 return;
6 if(sl==end_l && sr==end_r && sc==end_c) {
7 min = m;
8 return;
9 }
10 int i, tl, tr, tc;
11 for(i=0; i<6; i++) {
12 tl = sl + dl[i];
13 tr = sr + dr[i];
14 tc = sc + dc[i];
15 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
16 visited[tl][tr][tc] = 1;
17 dfs(tl, tr, tc, m+1);
18 visited[tl][tr][tc] = 0;
19 }
20 }
21 }
AC的BFS
1 #define MAX_SIZE 31
2 #define QUEUE_SIZE 100000
3 #define is_valid(l, r, c) (l>=0 && l<level && r>=0 && r<row && c>=0 && c<column)
4 char maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
5 int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE];
6 int level, row, column;
7 int begin_l, begin_r, begin_c;
8 int end_l, end_r, end_c;
9 /* direction: north, south, west, east, up, down */
10 const int dl[] = {0, 0, 0, 0, -1, 1};
11 const int dr[] = {-1, 1, 0, 0, 0, 0};
12 const int dc[] = {0, 0, -1, 1, 0, 0};
13 struct EACH {
14 int l, r, c;
15 int mins;
16 } queue[QUEUE_SIZE];
17 int head, tail;
18
19
20 void
21 init()
22 {
23 int i, j;
24 char *p;
25 memset(visited, 0, sizeof(visited));
26 memset(queue, 0, sizeof(queue));
27 head = -1;
28 tail = 0;
29 for(i=0; i<level; i++) {
30 for(j=0; j<row; j++) {
31 scanf("%s", maze[i][j]);
32 if((p=strchr(maze[i][j], 'S')) != NULL) {
33 begin_l = i;
34 begin_r = j;
35 begin_c = p-maze[i][j];
36 }
37 if((p=strchr(maze[i][j], 'E')) != NULL) {
38 end_l = i;
39 end_r = j;
40 end_c = p-maze[i][j];
41 }
42 }
43 getchar();
44 }
45 }
46
47 int
48 bfs()
49 {
50 int i, tl, tr, tc, cl, cr, cc, cm;
51 queue[tail].l = begin_l;
52 queue[tail].r = begin_r;
53 queue[tail].c = begin_c;
54 queue[tail].mins = 0;
55 visited[begin_l][begin_r][begin_c] = 1;
56 while(head < tail) {
57 ++head;
58 cl = queue[head].l;
59 cr = queue[head].r;
60 cc = queue[head].c;
61 cm = queue[head].mins;
62 if(cl==end_l && cr==end_r && cc==end_c)
63 return cm;
64 for(i=0; i<6; i++) {
65 tl = cl + dl[i];
66 tr = cr + dr[i];
67 tc = cc + dc[i];
68 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
69 visited[tl][tr][tc] = 1;
70 ++tail;
71 queue[tail].l = tl;
72 queue[tail].r = tr;
73 queue[tail].c = tc;
74 queue[tail].mins = cm+1;
75 }
76 }
77 }
78 return -1;
79 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3126思路:
BFS，一次AC
代码:
1 #define QUEUE_LEN 10000
2 int from, to;
3 int head, tail;
4 struct EACH {
5 int plen;
6 int num;
7 } queue[QUEUE_LEN];
8 int hash[QUEUE_LEN];
9
10 int
11 is_prime(int num)
12 {
13 int i, up = (int)sqrt(num*1.0);
14 for(i=2; i<=up; i++)
15 if(num%i == 0)
16 return 0;
17 return 1;
18 }
19
20 int
21 bfs()
22 {
23 int cur_plen, cur_num, next_num;
24 int i, j, k, t, div;
25 queue[tail].plen = 0;
26 queue[tail].num = from;
27 hash[queue[tail].num] = 1;
28 while(head < tail) {
29 ++head;
30 cur_plen = queue[head].plen;
31 cur_num = queue[head].num;
32 if(cur_num == to)
33 return cur_plen;
34 div = 1000;
35 t = cur_num;
36 for(i=3; i>=0; i--) {
37 k = t/div;
38 for(j=0; j<=9; j++) {
39 if(i==3 && j==0)
40 continue;
41 next_num = cur_num;
42 next_num -= k*div;
43 next_num += j*div;
44 if(!hash[next_num] && is_prime(next_num)) {
45 ++tail;
46 queue[tail].plen = cur_plen + 1;
47 queue[tail].num = next_num;
48 hash[queue[tail].num] = 1;
49 }
50 }
51 t = t%div;
52 div /= 10;
53 }
54 }
55 return -1;
56 }
// RS Hash Function
unsigned int RSHash( char * str)
{
unsigned int b = 378551 ;
unsigned int a = 63689 ;
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * a + ( * str ++ );
a *= b;
}
return (hash & 0x7FFFFFFF );
}
// JS Hash Function
unsigned int JSHash( char * str)
{
unsigned int hash = 1315423911 ;
while ( * str)
{
hash ^= ((hash << 5 ) + ( * str ++ ) + (hash >> 2 ));
}
return (hash & 0x7FFFFFFF );
}
// P. J. Weinberger Hash Function
unsigned int PJWHash( char * str)
{
unsigned int BitsInUnignedInt = (unsigned int )( sizeof (unsigned int ) * 8 );
unsigned int ThreeQuarters = (unsigned int )((BitsInUnignedInt * 3 ) / 4 );
unsigned int OneEighth = (unsigned int )(BitsInUnignedInt / 8 );
unsigned int HighBits = (unsigned int )( 0xFFFFFFFF ) << (BitsInUnignedInt - OneEighth);
unsigned int hash = 0 ;
unsigned int test = 0 ;
while ( * str)
{
hash = (hash << OneEighth) + ( * str ++ );
if ((test = hash & HighBits) != 0 )
{
hash = ((hash ^ (test >> ThreeQuarters)) & ( ~ HighBits));
}
}
return (hash & 0x7FFFFFFF );
}
// ELF Hash Function
unsigned int ELFHash( char * str)
{
unsigned int hash = 0 ;
unsigned int x = 0 ;
while ( * str)
{
hash = (hash << 4 ) + ( * str ++ );
if ((x = hash & 0xF0000000L ) != 0 )
hash ^= (x >> 24 );
hash &= ~ x;
}
return (hash & 0x7FFFFFFF );
}
// BKDR Hash Function
unsigned int BKDRHash( char * str)
{
unsigned int seed = 131 ; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * seed + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// SDBM Hash Function
unsigned int SDBMHash( char * str)
{
unsigned int hash = 0 ;
while ( * str)
{
hash = ( * str ++ ) + (hash << 6 ) + (hash << 16 ) - hash;
}
return (hash & 0x7FFFFFFF );
}
// DJB Hash Function
unsigned int DJBHash( char * str)
{
unsigned int hash = 5381 ;
while ( * str)
{
hash += (hash << 5 ) + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// AP Hash Function
unsigned int APHash( char * str)
{
unsigned int hash = 0 ;
int i;
for (i = 0 ; * str; i ++ )
{
if ((i & 1 ) == 0 )
{
hash ^= ((hash << 7 ) ^ ( * str ++ ) ^ (hash >> 3 ));
}
else
{
hash ^= ( ~ ((hash << 11 ) ^ ( * str ++ ) ^ (hash >> 5 )));
}
}
return (hash & 0x7FFFFFFF );
}
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3087思路:
类似于模拟题的BFS，判重使用的是字符串哈希，哈希函数: ELFHash(见PKU 2503)
代码:
1 int
2 shuffle()
3 {
4 int i, count = 0;
5 int hash_val;
6 memset(hash, 0, sizeof(hash));
7 while(1) {
8 for(i=0; i<2*len; i++) {
9 if(i%2==0)
10 queue[count][i] = tmp2[i/2];
11 else
12 queue[count][i] = tmp1[i/2];
13 }
14 queue[count][i] = '\0';
15 strncpy(tmp1, queue[count], len);
16 strncpy(tmp2, queue[count]+len, len);
17 if(strcmp(queue[count], desire) == 0)
18 return count+1;
19 if(search(queue[count]) != -1)
20 return -1;
21 hash_val = ELFHash(queue[count]);
22 insert(hash_val, count);
23 ++count;
24 }
25 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2503思路:
字符串哈希
这里使用的哈希函数是ELFHash
1 int ELFHash(char *str)
2 {
3 unsigned long t, hash = 0;
4 while(*str) {
5 hash = (hash<<4) + (*str++);
6 if((t = hash&0xF0000000L))
7 hash ^= t>>24;
8 hash &= ~t;
9 }
10 return (hash & 0x7FFFFFFF)%PRIME;
11 }
因为之前写哈希表解决冲突都是用的链接法，这里想尝试一下开放地址法，采用最简单的线性探查，结果居然TLE
无奈还是改成链接法，然后就AC了
不过，时间却有719MS之多，而网上几乎相同的代码只需要230MS左右，不知道是何原因
代码:
TLE的开放地址法
1 void
2 insert(int hash_val, int index)
3 {
4 if(!hash[hash_val].used) {
5 hash[hash_val].used = 1;
6 hash[hash_val].index = index;
7 } else
8 insert((hash_val+1)%PRIME, index); /* linear probing */
9 }
10
11 int
12 search(char *f_word)
13 {
14 int hash_val = ELFHash(f_word);
15 int i = 0;
16 while(1) {
17 if(!hash[hash_val].used || i==PRIME)
18 break;
19 if(strcmp(f_word, flg[hash[hash_val].index])==0)
20 return hash[hash_val].index;
21 hash_val = (hash_val+1)%PRIME;
22 ++i;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }
AC的链接法
1 void
2 insert(int hash_val, int index)
3 {
4 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
5 if(node == NULL) {
6 fprintf(stderr, "malloc error in: insert\n");
7 exit(1);
8 }
9 node->index = index;
10 node->next = hash[hash_val];
11 hash[hash_val] = node;
12 }
13
14 int
15 search(char *f_word)
16 {
17 int hash_val = ELFHash(f_word);
18 struct Node *node = hash[hash_val];
19 while(node != NULL) {
20 if(strcmp(f_word, flg[node->index]) == 0)
21 return node->index;
22 node = node->next;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }