2015年2月18日 星期三

2015/02/18 Codeforces 515D. Drazil and Tiles

/*
    寫法感覺 
    跟拓撲排序很像 OwO
*/
// http://codeforces.com/problemset/problem/515/D
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

int N, M;
char c[3000][3000];
int dir[3000][3000];

int cnt;

int vx[] = {1, 0, -1, 0};
int vy[] = {0, 1, 0, -1};

void pull(int x, int y)
{
    if( 0 > x || x >= N ) return;
    if( 0 > y || y >= M ) return;

    dir[x][y] = 0;
    if( c[x][y] != '.' ) return;

    for(int vi = 0; vi < 4; vi++)
    {
        int nx = x+vx[vi];
        int ny = y+vy[vi];

        if( 0 > nx || nx >= N ) continue;
        if( 0 > ny || ny >= M ) continue;

        if( c[nx][ny] == '.' ) dir[x][y]++;
    }
}

typedef pair<int, int> xy;
#define x first
#define y second

queue<xy> que;

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%s", c[Ni]);

    cnt = 0;

    for(int Ni = 0; Ni < N; Ni++)
        for(int Mi = 0; Mi < M; Mi++)
        {
            if( c[Ni][Mi] == '.' ) cnt++;
            pull(Ni, Mi);

            if( dir[Ni][Mi] == 1 )
                que.push(xy(Ni, Mi) );
        }

    while( !que.empty() )
    {
        xy F = que.front();
        que.pop();

        int sx = F.x, sy = F.y;

        for(int vi = 0; vi < 4; vi++)
        {
            int nx = sx+vx[vi];
            int ny = sy+vy[vi];

            if( 0 > nx || nx >= N ) continue;
            if( 0 > ny || ny >= M ) continue;

            if( c[nx][ny] != '.' ) continue;

            cnt -= 2;

            if( vi == 0 )
            {
                c[sx][sy] = '^';
                c[nx][ny] = 'v';
            }
            if( vi == 1 )
            {
                c[sx][sy] = '<';
                c[nx][ny] = '>';
            }
            if( vi == 2 )
            {
                c[sx][sy] = 'v';
                c[nx][ny] = '^';
            }
            if( vi == 3 )
            {
                c[sx][sy] = '>';
                c[nx][ny] = '<';
            }

            pull(nx, ny);

            for(int vj = 0; vj < 4; vj++)
            {
                int ex = nx+vx[vj];
                int ey = ny+vy[vj];

                if( 0 > ex || ex >= N ) continue;
                if( 0 > ey || ey >= M ) continue;

                pull(ex, ey);
                if( dir[ex][ey] == 1 )
                    que.push(xy(ex, ey) );
            }
        }
    }

    if( cnt ) puts("Not unique");
    else
    {
        for(int Ni = 0; Ni < N; Ni++)
            printf("%s\n", c[Ni]);
    }
}

沒有留言:

張貼留言