CodeForces - 516B Drazil and Tiles（bfs）

https://vjudge.net/problem/CodeForces-516B

题意

在一个n*m图中放1*2或者2*1的长方形，问是否存在唯一的方法填满图中的‘.’

分析

如果要有唯一的方案，那么必定存在度为一的点，因为只有这样，把这一格以及它相邻的涂掉的方案才唯一，然后可能产生新的度为一的可行点，不断更新，bfs寻找这样的点。最后检测一遍是否还有‘.'存在即可。

#include<iostream>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)

#define rep1(i,e) for(int i=1;i<=(e);i++)

#define repx(i,x,e) for(int i=(x);i<=(e);i++)

#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

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

#define scdd(a,b) scanf("%d%d",&a,&b)

#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define pd(a) printf("%d\n",a)

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

#define scll(a,b) scanf("%lld%lld",&a,&b)

#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

#define IOS ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

typedef long long ll;

template <class T>

void test(T a){cout<<a<<endl;}

template <class T,class T2>

void test(T a,T2 b){cout<<a<<" "<<b<<endl;}

template <class T,class T2,class T3>

void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const ll mod = 1e9+;

int T;

void testcase(){

    printf("Case %d: ",++T);

}

const int MAXN = ;

const int MAXM = ;

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

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

int code[]={'<','v','^','>'};

int n,m;

char g[MAXN][MAXN];

bool check(int x,int y){

    return (x>=&&x<n&&y>=&&y<m&&g[x][y]=='.');

}

int deg(int i,int j){

    int d=;

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

        int ni=i+dx[k];

        int nj=j+dy[k];

        if(check(ni,nj)) d++;

    }

    return d;

}

void bfs(){

    queue< pair<int,int> > que;

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

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

            if(deg(i,j)==&&g[i][j]=='.')

                que.push(MP(i,j));

        }

    }

    while(!que.empty()){

        int x=que.front().X,y=que.front().Y;

        que.pop();

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

            int nx = x+dx[i];

            int ny = y+dy[i];

            if(check(nx,ny)){

                g[x][y]=code[i];

                g[nx][ny]=code[-i];

//                printf("(%d,%d)-(%d,%d)--%d\n",x,y,nx,ny,i);

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

                    int nnx = nx+dx[j];

                    int nny = ny+dy[j];

                    if(check(nnx,nny)&&deg(nnx,nny)==){

                       que.push(MP(nnx,nny));

                    }

                }

                break;

            }

        }

    }

}

int main() {

#ifdef LOCAL

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

#endif // LOCAL

    scdd(n,m);

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

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

    }

    bfs();

    int f=;

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

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

            if(g[i][j]=='.'){

                f=;

                break;

            }

        }

    }

    if(f) puts("Not unique");

    else{

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

            puts(g[i]);

    }

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

//            puts(g[i]);

    return ;

}

Drazil and Tiles

CodeForces - 516B