欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018 ICPC南京区域赛 K .Kangaroo Puzzle

程序员文章站 2022-03-30 16:38:06
...

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

 

相关标签: 玄学