【题目链接】:http://codeforces.com/contest/515/problem/D

【题意】



给你一个n*m的格子;

然后让你用1*2的长方形去填格子的空缺;

如果有填满的方案且方案是唯一的;

则输出那个方案,否则,输出不唯一;

【题解】



记录每个点的度;

每个点的度,为这个点4个方向上空格的个数;

优先处理度数为1的点;

这些点的摆放方式肯定是唯一的;

摆完这些点(两个之后),与之相连的点的度数都减1；

看看有没有新的度数为1的点;

很像拓扑排序对吧。

最后看看占据的点是不是n*m个



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 2e3+100;

struct abc

{

    int x, y;

};

int n, m,du[N][N],cnt = 0;

char s[N][N];

bool bo[N][N];

queue <abc> dl;

void cl(int x, int y)

{

    rep1(j, 1, 4)

    {

        int x1 = x + dx[j], y1 = y + dy[j];

        du[x1][y1]--;

        if (bo[x1][y1] && du[x1][y1] == 1)

            dl.push({ x1,y1 });

    }

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    memset(bo, false, sizeof bo);

    rei(n), rei(m);

    rep1(i, 1, n)

    {

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

        rep1(j, 1, m)

            if (s[i][j] == '.')

                bo[i][j] = true;

            else

                bo[i][j] = false,cnt++;

    }

    rep1(i,1,n)

        rep1(j,1,m)

        if (bo[i][j])

        {

            int num = 0;

            rep1(k, 1, 4)

                num += bo[i + dx[k]][j + dy[k]];

            du[i][j] = num;

            if (du[i][j] == 1)

            {

                dl.push({ i,j });

            }

        }

    while (!dl.empty())

    {

        int x0 = dl.front().x, y0 = dl.front().y;

        dl.pop();

        rep1(j, 1, 4)

        {

            int x = x0 + dx[j], y = y0 + dy[j];

            /*

            const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

            const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

            */

            if (bo[x][y])

            {

                if (j == 1) s[x0][y0] = '^', s[x][y] = 'v';

                if (j == 2) s[x0][y0] = 'v', s[x][y] = '^';

                if (j == 3)s[x0][y0] = '>', s[x][y] = '<';

                if (j == 4) s[x0][y0] = '<', s[x][y] = '>';

                bo[x][y] = bo[x0][y0] = false;

                cl(x, y), cl(x0, y0);

                cnt += 2;

                break;

            }

        }

    }

    if (cnt == n*m)

    {

        rep1(i, 1, n)

            puts(s[i] + 1);

    }

    else

        puts("Not unique");

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}