思路:首先需要明确我们只要每次操作合并两个,那么总能使得最后合并成一个。下面我们给出两个点合并的方法,先任意选择两个点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;
}