首页 > 代码库 > 【HDOJ】3500 Fling

【HDOJ】3500 Fling

2024-07-29 00:48:25   219人阅读

题意巨难懂。简言之，就是球互相碰撞时，主动碰撞的球将会停止，另一个球将沿着碰撞方向继续移动，不断碰撞。但是无法弹射紧挨着的球，但是若a弹射b，bc相邻，这种情况b可以弹射c。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6   7 #define MAXN 10  8   9 typedef struct { 10     int x, y; 11     char d; 12 } node_t; 13  14 node_t nodes[15]; 15 char map[MAXN][MAXN]; 16 int on; 17 // U < L < R < D. 18 int dir[4][2] = {-1,0,0,-1,0,1,1,0}; 19  20 bool check(int x, int y) { 21     return x<0||x>=7||y<0||y>=8; 22 } 23  24 char getDir(int k) { 25     if (k==0) return ‘U‘; 26     if (k==1) return ‘L‘; 27     if (k==2) return ‘R‘; 28     return ‘D‘; 29 } 30  31 bool dfs(int n) { 32     int i, j, k, x, y; 33     bool flag; 34  35     if (n == 0) 36         return true; 37  38     for (i=0; i<7; ++i) { 39         for (j=0; j<8; ++j) { 40             if (map[i][j] == ‘O‘) { 41                 for (k=0; k<4; ++k) { 42                     x = i + dir[k][0]; 43                     y = j + dir[k][1]; 44                     if (check(x, y) || map[x][y]==‘O‘) 45                         continue; 46                     flag = false; 47                     while (!check(x, y)) { 48                         if (map[x][y] == ‘O‘) { 49                             flag = true; 50                             map[x][y] = ‘X‘; 51                             map[x-dir[k][0]][y-dir[k][1]] = ‘O‘; 52                         } 53                         x += dir[k][0]; 54                         y += dir[k][1]; 55                     } 56                     if (flag) { 57                         map[i][j] = ‘X‘; 58                         nodes[n].x = i; 59                         nodes[n].y = j; 60                         nodes[n].d = getDir(k); 61                         if (dfs(n-1)) 62                             return true; 63                         do { 64                             x -= dir[k][0]; 65                             y -= dir[k][1]; 66                             if (map[x][y] == ‘O‘) { 67                                 map[x][y] = ‘X‘; 68                                 map[x+dir[k][0]][y+dir[k][1]] = ‘O‘; 69                             } 70                         } while (x!=i || y!=j); 71                         map[i][j] = ‘O‘; 72                     } 73                 } 74             } 75         } 76     } 77  78     return false; 79 } 80  81 int main() { 82     int i = 0, j; 83     int t = 0; 84  85 #ifndef ONLINE_JUDGE 86     freopen("data.in", "r", stdin); 87 #endif 88  89     while (scanf("%s", &map[i]) != EOF) { 90         for (i=1; i<7; ++i) 91             scanf("%s", &map[i]); 92         on = 0; 93         for (i=0; i<7; ++i) 94             for (j=0; j<8; ++j) 95                 if (map[i][j] == ‘O‘) 96                     ++on; 97         dfs(on-1); 98  99         if (t != 0)100             printf("\n");101         printf("CASE #%d:\n", ++t);102         for(i=on-1; i>=1; --i)103             printf("%d %d %c\n", nodes[i].x, nodes[i].y, nodes[i].d);104         getchar();105         i = 0;106     }107 108     return 0;109 }

 

【HDOJ】3500 Fling


联系
我们