2018 ICPC南京区域赛 K .Kangaroo Puzzle

 思路：首先需要明确我们只要每次操作合并两个，那么总能使得最后合并成一个。下面我们给出两个点合并的方法，先任意选择两个点a和b，求出两个点之间的最短路。然后让所有点都按照该路径进行移动。那么最后a点会到达b点，b点会到达c。

下面我们证明 现在的状态不会和原来的状态重合（因为状态总数为有限个，我们只需要证明状态的转移过程中不会产生环即可）

状态的组成可看做两种要素，第一是所有1的相对状态，第二是所有1相对地图的位置。

下面用反证法，假设一个状态可以回到他之前的状态，那么所有1的相对状态不变，所以所有1在转移的过程中不可以撞墙。

其次若想回到原来的绝对位置，那么我们有两种选择，一种是原路返回，一种是所有的1绕一个环，回到原来的状态。（都是在所有1不撞墙的前提下）。而题目说1无环，那么只可能是原路返回。所以我们只要在追赶的过程中不走回头路，那么由于状态数是有限的总能遍历到两点的距离为0的情况。这时两点重合，追及成功。

所有我从别人的博客中学到了随机化的方法，实在是太骚了。。。

坑点：随机化

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef int lint;
lint a[30][30],b[30][30],vis[30][30],c[30][30];
typedef pair<lint,lint> pii;
vector<lint> ans,ve;
pii dir[4];
lint n,m;
bool dfs( lint x,lint y,const pii & b ){
    vis[x][y] = 1;
    if( x == b.first && y == b.second ){
        return true;
    }
    for( lint i = 0;i < 4;i++ ){
        lint xx = x + dir[i].first;
        lint yy = y + dir[i].second;
        if( xx < 1 || xx >n || yy < 1 || yy > m || vis[xx][yy] || a[xx][yy] == 0 ) continue;
        ans.push_back( i );ve.push_back(i);
        if(dfs(xx,yy,b)) return true;
    }
    ve.pop_back();
    ans.pop_back();
    vis[x][y] = 0;
    return false;
}
void step( lint x,lint y,lint k ){
        lint xx = x + dir[ve[k]].first;
        lint yy = y + dir[ve[k]].second;
        if( xx > 0 && xx <= n && yy > 0 && yy <= m && b[xx][yy] != -1 ){
            c[xx][yy] += b[x][y];
            b[x][y] = 0;
        }
}
void solve( const pii& aa,const pii & bb  ){
    memset( vis,0,sizeof(vis) );
    //memset( c,0,sizeof(c) );
    ve.clear();
    vis[aa.first][aa.second] = 1;
    dfs(aa.first,aa.second,bb);
    for( lint k = 0;k < ve.size();k++ ) {
        memset( c,0,sizeof(c) );
        for (lint i = 1; i <= n; i++) {
            for (lint j = 1; j <= m; j++) {
                if (b[i][j] > 0) {
                    step(i, j,k);
                }
            }
        }
        for (lint i = 1; i <= n; i++) {
            for (lint j = 1; j <= m; j++) {
                b[i][j] += c[i][j];
            }
        }
    }
}
void prework(){
    dir[0].first = 0;dir[0].second = 1;
    dir[1].first = 1;dir[1].second = 0;
    dir[2].first = 0;dir[2].second = -1;
    dir[3].first = -1;dir[3].second = 0;
}
int main(){
    prework();
    lint cnt = 0;
    scanf("%d%d",&n,&m);
    for( lint i = 1;i <= n;i++ ){
        for( lint j = 1;j <= m;j++ ){
            scanf("%1d",&a[i][j]);
            if( a[i][j] == 1 ){
                b[i][j] = 1;
            }else{
                b[i][j] = -1;
            }
        }
    }
    while(1){
        lint cc = 0;
        pii s,t;
        for( lint i = 1;i <= n;i++ ){
            for( lint j = 1;j <= m;j++ ){
                if( b[i][j] > 0 ){
                    cc++;
                    if( cc == 1 ){
                        s.first = i;s.second = j;
                    }else{
                        t.first = i;t.second = j;
                    }
                }
                if( cc == 2 ) break;
            }
            if( cc == 2 ) break;
        }
        if( cc == 2 )
        solve(s,t);
        cnt = 0;
        for( lint i =1;i <= n;i++ ){
            for( lint j = 1;j <= m;j++ ){
                if( b[i][j] > 0 ) cnt ++;
            }
        }
        if( cnt <= 1 ) break;
    }
    for( lint i = 0;i < ans.size();i++ ){
        if( ans[i] == 0 ){
            printf("R");
        }else if( ans[i] == 1 ){
            printf("D");
        }else if( ans[i] == 2 ){
            printf("L");
        }else{
            printf("U");
        }
    }
    return 0;
}