2016年5月23日 星期一

UVA 1015 Partitions

/*    
    題目連結

    不難想但輸入和處理都有點麻煩的題目

    原本以為partition 會是一刀一刀切出來的
    結果不是 而且其實題敘裡就有這樣的例子了 XD
   
    (並不是在每一筆畫 畫上去的時候 都會形成長方形)

    看到第一眼的想法會是 一個取交集 一個取聯集
    但是取交集 可能會跑出一堆不是長方形的"渣渣"

    那解決辦法是 我們找出"視覺上的一個個聯通塊"
    把包含那個聯通塊的 最小長方形內的渣渣都清掉
    要注意 這樣可能會產生新的渣渣 所以要繼續清
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int H, W;

char A[30][50], B[30][50];
char D[30][50];

bool visit[30][50];

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

bool process(int sx, int sy)
{
    fill(visit[0], visit[0]+sizeof(visit), false);

    queue<int> que;

    int mxx = sx, mnx = sx, mxy = sy, mny = sy;
    visit[sx][sy] = true;
    que.push(sx); que.push(sy);

    while( !que.empty() )
    {
        int x = que.front(); que.pop();
        int y = que.front(); que.pop();

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

            if( 0 > nx || nx > H ) continue;
            if( 0 > ny || ny > W*2 ) continue;

            if( vi == 0 && D[nx][ny] == '_' ) continue;
            if( vi == 1 && D[x][y+1] == '|' ) continue;
            if( vi == 2 && D[x][y] == '_' ) continue;
            if( vi == 3 && D[x][y-1] == '|' ) continue;

            if( !visit[nx][ny] )
            {
                visit[nx][ny] = true;
                mxx = max(mxx, nx), mnx = min(mnx, nx);
                mxy = max(mxy, ny), mny = min(mny, ny);

                que.push(nx), que.push(ny);
            }
        }
    }

    bool erase = false;

    for(int i = mnx; i <= mxx; i++)
        for(int j = mny+1; j <= mxy; j += 2)
            if( D[i][j] != ' ' )
            {
                D[i][j] = ' ';
                erase = true;
            }

    for(int i = mnx; i < mxx; i++)
        for(int j = mny; j <= mxy; j += 2)
            if( D[i][j] != ' ' )
            {
                D[i][j] = ' ';
                erase = true;
            }

    return erase;
}

int Ti = 0;

int main()
{
    while(1)
    {
        scanf("%d %d%*[^\n]", &W, &H);
        getchar();

        if( !W && !H ) break;

        fill(A[0], A[0]+sizeof(A), ' ');
        fill(B[0], B[0]+sizeof(B), ' ');

        for(int Hi = 0; Hi <= H; Hi++)
        {
            for(int Wi = 0; Wi <= W*2; Wi++)
                A[Hi][Wi] = getchar();

            getchar();

            for(int Wi = 0; Wi <= W*2; Wi++)
                B[Hi][Wi] = getchar();

            scanf("%*[^\n]");
            getchar();
        }

        fill(D[0], D[0]+sizeof(D), ' ');

        for(int Hi = 0; Hi <= H; Hi++)
            for(int Wi = 0; Wi <= W*2; Wi++)
                if( A[Hi][Wi] == B[Hi][Wi] )
                    D[Hi][Wi] = A[Hi][Wi];

        for(int Hi = 1; Hi <= H; Hi++)
            for(int Wi = 1; Wi <= W*2; Wi+=2)
                while(process(Hi, Wi) );

        printf("Case %d:\n", ++Ti);

        for(int Hi = 0; Hi <= H; Hi++)
        {
            for(int Wi = 0; Wi <= W*2; Wi++)
                if( A[Hi][Wi] != ' ' ) printf("%c", A[Hi][Wi]);
                else if( B[Hi][Wi] != ' ' ) printf("%c", B[Hi][Wi]);
                else printf(" ");

            printf(" ");

            for(int Wi = 0; Wi <= W*2; Wi++)
                printf("%c", D[Hi][Wi]);

            puts("");
        }

        puts("");
    }
}

沒有留言:

張貼留言