发上昨天的题。这两天考试多作业多顾不上做题了T_T
poj3278 - Catch That Cow
大意：从n出发，问抵达k的最少时间。两种移动方式：1.从点x移动到x-1或x+1 2.从点x移动到2x
题解：BFS。上限是max(n, k) * 10。扩大了10倍左右差不多够用了。
1 #include <stdio.h> 2 3 int f[1000013]; 4 int d[1000013]; 5 int s, t; 6 7 int max(int x, int y) { 8 return x > y ? x : y; 9 } 10 11 12 int main() { 13 int n, k; 14 scanf("%d%d", &n, &k); 15 int m = max(n * 10, k * 10); 16 for (int i = 0; i <= m; i++) { 17 f[i] = -1; 18 } 19 f[n] = 0; 20 d[0] = n; 21 if (f[k] == -1) { 22 for (int l = 0, r = 1, w = 0; !w; l++) { 23 int a[3] = {d[l] << 1, d[l] + 1, d[l] - 1}; 24 for (int i = 0; i < 3; i++) { 25 if (0 <= a[i] && a[i] <= m && f[a[i]] == -1) { 26 f[a[i]] = f[d[l]] + 1; 27 if (a[i] == k) { 28 w = 1; 29 break; 30 } 31 d[r++] = a[i]; 32 } 33 } 34 } 35 } 36 printf("%d\n", f[k]); 37 return 0; 38 }
poj2632 - Crashing Robots
大意：地图上有n个机器人，给出坐标和初始朝向。每次可以移动一个机器人或改变一个机器人的朝向。若机器人撞上墙或其他机器人，则输出相应信息。
题解：纯模拟。。。
1 #include <stdio.h> 2 #include <string.h> 3 4 //N->(0, 1) E->(1, 0) S->(0, -1) W->(-1, 0) 5 //L-> t = (t + 3) % 4 6 //R-> t = (t + 1) % 4 7 8 int x[200], y[200], t[200]; 9 int has[200][200]; 10 int move[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 11 char s[3]; 12 13 int main() { 14 int a, b, z, n, m; 15 scanf("%d", &z); 16 while (z--) { 17 memset(has, 0, sizeof(has)); 18 scanf("%d%d", &a, &b); 19 scanf("%d%d", &n, &m); 20 for (int i = 1; i <= n; i++) { 21 scanf("%d%d%s", &x[i], &y[i], s); 22 switch (s[0]) { 23 case ‘N‘: 24 t[i] = 0; 25 break; 26 case ‘E‘: 27 t[i] = 1; 28 break; 29 case ‘S‘: 30 t[i] = 2; 31 break; 32 case ‘W‘: 33 t[i] = 3; 34 break; 35 } 36 has[x[i]][y[i]] = i; 37 } 38 int f1 = 0, f2 = 0, f3 = 0; 39 for (int i = 0; i < m; i++) { 40 int k, r; 41 scanf("%d%s%d", &k, s, &r); 42 if (f1 || f2) { 43 continue; 44 } 45 for (int i = 0; i < r && !f1 && !f2; i++) { 46 switch (s[0]) { 47 case ‘F‘: 48 has[x[k]][y[k]] = 0; 49 x[k] += move[t[k]][0]; 50 y[k] += move[t[k]][1]; 51 if (x[k] == 0 || x[k] > a || y[k] == 0 || y[k] > b) { 52 f1 = k; 53 } else if (has[x[k]][y[k]]) { 54 f2 = k; 55 f3 = has[x[k]][y[k]]; 56 } 57 has[x[k]][y[k]] = k; 58 break; 59 case ‘L‘: 60 t[k] = (t[k] + 3) % 4; 61 break; 62 case ‘R‘: 63 t[k] = (t[k] + 1) % 4; 64 break; 65 } 66 } 67 } 68 if (f1) { 69 printf("Robot %d crashes into the wall\n", f1); 70 } else if (f2) { 71 printf("Robot %d crashes into robot %d\n", f2, f3); 72 } else { 73 printf("OK\n"); 74 } 75 } 76 return 0; 77 }
poj2049 - Finding Nemo
大意：给出一副地图上m道墙和n扇门的描述信息以及Nemo的位置。问寻找到Nemo最少经过几道墙。
题解：标记一个格子的上方和右方的障碍物类型（墙/门/无障碍)，然后搜索。从一个点移动到另一个点有两种情况。如果是无障碍的，直接加入搜索队列，若通过的是门，加入一个缓冲队列，搜索队列空了后，将缓冲队列的数据移入搜索队列。这题特别注意虽然墙和门的位置在[1, 199]内，但Nemo的位置可能不在这个范围（害我WA了T_T)。这样答案就是0。
1 //f[i][j][2];->up/right of (i, j) 2 //x y 0 d -> f[x][y-1][0] : f[x+d][y-1][0] 3 //x y 1 d -> f[x-1][y][1] : f[x-1][y+d][1] 4 #include <stdio.h> 5 #include <string.h> 6 7 int dir[2][2] = {{1, 0}, {0, 1}}; 8 int move[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 9 int f[205][205][2]; 10 int h[200000][2]; 11 int g[100000][2]; 12 int go[205][205]; 13 14 int judge(int x, int y, int tx, int ty) { 15 if (tx < 0 || tx > 199 || ty < 0 || ty > 199 || go[tx][ty]) { 16 return -1; 17 } 18 if (x < tx) { 19 return f[x][y][1]; 20 } else if (x > tx) { 21 return f[tx][ty][1]; 22 } else if (y < ty) { 23 return f[x][y][0]; 24 } else { 25 return f[tx][ty][0]; 26 } 27 } 28 29 30 int main() { 31 int n, m, x, y, t, d; 32 int sx, sy, fx, fy; 33 while (~scanf("%d%d", &m, &n) && m != -1) { 34 memset(f, 0, sizeof(f)); 35 memset(go, 0, sizeof(go)); 36 for (int i = 0; i < m; i++) { 37 scanf("%d%d%d%d", &x, &y, &d, &t); 38 for (int i = 1; i <= t; i++) { 39 f[x - 1 + dir[d][0] * i][y - 1 + dir[d][1] * i][d] = 1; 40 } 41 } 42 for (int i = 0; i < n; i++) { 43 scanf("%d%d%d", &x, &y, &d); 44 f[x - 1 + dir[d][0]][y - 1 + dir[d][1]][d] = 2; 45 } 46 double u1, u2; 47 scanf("%lf%lf", &u1, &u2); 48 fx = (int)u1; 49 fy = (int)u2; 50 int now = 0, flag = 0; 51 if (fx < 0 || fx > 199 || fy < 0 || fy > 199) { 52 flag = 1; 53 } 54 h[0][0] = h[0][1] = 0; 55 go[0][0] = 1; 56 int l = 0, r = 1, v = 0; 57 while (!flag && l < r) { 58 x = h[l][0]; 59 y = h[l][1]; 60 if (x == fx && y == fy) { 61 flag = 1; 62 break; 63 } 64 for (int i = 0; i < 4; i++) { 65 int tx = x + move[i][0]; 66 int ty = y + move[i][1]; 67 int k = judge(x, y, tx, ty); 68 if (!k) { 69 go[tx][ty] = 1; 70 h[r][0] = tx; 71 h[r++][1] = ty; 72 } else if (k == 2) { 73 g[v][0] = tx; 74 g[v++][1] = ty; 75 } 76 } 77 l++; 78 if (l == r) { 79 for (int i = 0; i < v; i++) { 80 h[r][0] = g[i][0]; 81 h[r++][1] = g[i][1]; 82 go[g[i][0]][g[i][1]] = 1; 83 } 84 v = 0; 85 now++; 86 } 87 } 88 printf("%d\n", flag ? now : -1); 89 } 90 return 0; 91 }
poj训练计划-2(3278/2632/2049),布布扣,bubuko.com
原文：http://www.cnblogs.com/nilmo/p/3570563.html