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

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

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

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

 #include <bits/stdc++.h>

 #define sd(a) scanf("%d",&a)

 #define sld(a) scanf("%lld",&a)

 #define mst(a,b) memset(a,b,sizeof a)

 #define mp make_pair

 #define all(a) a.begin(),a.end()

 typedef long long ll;

 #define pb push_back

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 2e6 + ;

 const int maxm = 1e6 +  ;

 const int inf = 0x3f3f3f3f;

 const ll mod = 1e9 + ;

 const double eps = 1e-;

 char s[][];

 int to[][][][];

 bool vis[][];

 vector<pii>v;

 int n, m;

 bool judge(int x, int y) {

     return  <= x && x <= n &&  <= y && y <= m && s[x][y] == '';

 }

 int dx[] = {, , -, }, dy[] = {, , , -};

 void pre(int x, int y) {

     mst(vis, );

     vis[x][y] = ;

     vector<pii>v;

     queue<pii>q;

     for(int i = ; i < ; ++i) {

         v.clear();

         int nx = x + dx[i], ny = y + dy[i];

         if(!judge(nx, ny))

             continue;

         q.push(mp(nx, ny));

         for(; !q.empty();) {

             pii p = q.front();

             q.pop();

             int ux = p.first;

             int uy = p.second;

             if(vis[ux][uy])

                 continue;

             vis[ux][uy] = ;

             v.pb(p);

             for(int j = ; j < ; ++j) {

                 int qx = dx[j] + ux, qy = dy[j] + uy;

                 if(judge(qx, qy) && !vis[qx][qy])

                     q.push(mp(qx, qy));

             }

         }

         int sz = v.size();

         for(int j = ; j < sz; ++j) {

             int qx = v[j].first;

             int qy = v[j].second;

             to[x][y][qx][qy] = i;

         }

     }

 }

 int main() {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif // local

 //    int n,m;

     sd(n), sd(m);

     for(int i = ; i <= n; ++i)

         scanf("%s", s[i] + );

     for(int i = ; i <= n; ++i)

         for(int j = ; j <= m; ++j) {

             if(s[i][j] - '')

                 v.pb(mp(i, j));

             pre(i, j);

         }

     vector<int>q;

     int sz = v.size();

     char ch[] = {'D', 'R', 'U', 'L'};

     for(;;) {

         int idx1 = , idx2 = -;

         for(int i = ; i < sz; ++i) {

             if(v[i] != v[idx1]) {

                 idx2 = i;

                 break;

             }

         }

         if(idx2 == -)

             break;

         for(; v[idx1] != v[idx2];) {

             int x1 = v[idx1].first, x2 = v[idx2].first;

             int y1 = v[idx1].second, y2 = v[idx2].second;

             int id = to[x1][y1][x2][y2];

             q.pb(id);

             for(int i = ; i < sz; ++i) {

                 if(judge(v[i].first + dx[id], v[i].second + dy[id]))

                     v[i].first += dx[id], v[i].second += dy[id];

             }

         }

     }

     for(int i = , z = q.size(); i < z; ++i) {

         int id = q[i];

         putchar(ch[id]);

     }

     return ;

 }