ACM-ICPC 2018 南京赛区现场赛 K. Kangaroo Puzzle （思维+构造）

题目链接：https://codeforc.es/gym/101981/attachments

题意：在 n * m 的平面上有若干个袋鼠和墙（1为袋鼠，0为墙），每次可以把所有袋鼠整体往一个方向移动一步（不能走出边界和不能走到墙），为在不超过5e4步的情况下能否把全部袋鼠聚集在同一个位置。

题解：先预处理每个袋鼠到其他袋鼠的初始方向，然后每次选两个不同的袋鼠，其中一个向另一个逼近，直到聚集在一起，然后重复该操作。因为n，m <= 20，所以最多只有400个袋鼠，而每两个不同的袋鼠逼近的过程中最多走 80 步，故操作次数上界是 3.2e4。

 

  1 #include <bits/stdc++.h>
  2 #define sd(a) scanf("%d",&a)
  3 #define sld(a) scanf("%lld",&a)
  4 #define mst(a,b) memset(a,b,sizeof a)
  5 #define mp make_pair
  6 #define all(a) a.begin(),a.end()
  7 typedef long long ll;
  8 #define pb push_back
  9 using namespace std;
 10 typedef pair<int, int> pii;
 11 const int maxn = 2e6 + 10;
 12 const int maxm = 1e6 +  10;
 13 const int inf = 0x3f3f3f3f;
 14 const ll mod = 1e9 + 7;
 15 const double eps = 1e-9;
 16 char s[33][33];
 17 int to[33][33][33][33];
 18 bool vis[33][33];
 19 vector<pii>v;
 20 int n, m;
 21 
 22 bool judge(int x, int y) {
 23     return 1 <= x && x <= n && 1 <= y && y <= m && s[x][y] == '1';
 24 }
 25 
 26 int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
 27 void pre(int x, int y) {
 28     mst(vis, 0);
 29     vis[x][y] = 1;
 30     vector<pii>v;
 31     queue<pii>q;
 32     for(int i = 0; i < 4; ++i) {
 33         v.clear();
 34         int nx = x + dx[i], ny = y + dy[i];
 35         if(!judge(nx, ny))
 36             continue;
 37         q.push(mp(nx, ny));
 38         for(; !q.empty();) {
 39             pii p = q.front();
 40             q.pop();
 41             int ux = p.first;
 42             int uy = p.second;
 43             if(vis[ux][uy])
 44                 continue;
 45             vis[ux][uy] = 1;
 46             v.pb(p);
 47             for(int j = 0; j < 4; ++j) {
 48                 int qx = dx[j] + ux, qy = dy[j] + uy;
 49                 if(judge(qx, qy) && !vis[qx][qy])
 50                     q.push(mp(qx, qy));
 51             }
 52         }
 53         int sz = v.size();
 54         for(int j = 0; j < sz; ++j) {
 55             int qx = v[j].first;
 56             int qy = v[j].second;
 57             to[x][y][qx][qy] = i;
 58         }
 59     }
 60 }
 61 
 62 int main() {
 63 #ifdef LOCAL
 64     freopen("in", "r", stdin);
 65 #endif // local
 66 //    int n,m;
 67     sd(n), sd(m);
 68     for(int i = 1; i <= n; ++i)
 69         scanf("%s", s[i] + 1);
 70     for(int i = 1; i <= n; ++i)
 71         for(int j = 1; j <= m; ++j) {
 72             if(s[i][j] - '0')
 73                 v.pb(mp(i, j));
 74             pre(i, j);
 75         }
 76     vector<int>q;
 77     int sz = v.size();
 78     char ch[] = {'D', 'R', 'U', 'L'};
 79     for(;;) {
 80         int idx1 = 0, idx2 = -1;
 81         for(int i = 1; i < sz; ++i) {
 82             if(v[i] != v[idx1]) {
 83                 idx2 = i;
 84                 break;
 85             }
 86         }
 87         if(idx2 == -1)
 88             break;
 89         for(; v[idx1] != v[idx2];) {
 90             int x1 = v[idx1].first, x2 = v[idx2].first;
 91             int y1 = v[idx1].second, y2 = v[idx2].second;
 92             int id = to[x1][y1][x2][y2];
 93             q.pb(id);
 94             for(int i = 0; i < sz; ++i) {
 95                 if(judge(v[i].first + dx[id], v[i].second + dy[id]))
 96                     v[i].first += dx[id], v[i].second += dy[id];
 97             }
 98         }
 99     }
100     for(int i = 0, z = q.size(); i < z; ++i) {
101         int id = q[i];
102         putchar(ch[id]);
103     }
104     return 0;
105 }