Wednesday, April 29, 2015

UVa - 785 - Grid Colouring

#include <bits/stdc++.h>
#define S 33
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

string Grid[S];
int len[S], ind, vis[S][S+50], vis2[S][S+50];
char tmp, tp;

void dfs2(int i, int j){
    if(i < 0 || j < 0 || i >= ind || j >= len[i] || vis2[i][j])return;
    if(Grid[i][j] != ' ' && Grid[i][j] != tp)return;
    vis2[i][j] = 1;
    Grid[i][j] = tp;
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs2(px, py);
    }
}

void dfs(int i, int j){
    if(i < 0 || j < 0 || i >= ind || j >= len[i] || vis[i][j])return;
    vis[i][j] = 1;
    if(Grid[i][j] != ' ' && Grid[i][j] != tmp){
        tp = Grid[i][j];
        dfs2(i, j);
    }
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int main(){
    while(getline(cin, Grid[0])){
        ind = 1; len[0] = Grid[0].size();
        while(getline(cin, Grid[ind])){
            len[ind] = Grid[ind].size();
            if(Grid[ind][0] == '_')break;
            ind++;
        }
        memset(vis, 0, sizeof(vis));
        memset(vis2, 0, sizeof(vis2));
        for(int i = 0; i < ind; i++){
            for(int j = 0; j < len[i]; j++){
                if(Grid[i][j] != ' '){
                    tmp = Grid[i][j];
                    dfs(i, j);
                }
            }
        }
        for(int i = 0; i <= ind; i++){
            for(int j = 0; j < len[i]; j++){
                cout << Grid[i][j];
            }
            puts("");
        }
    }
    return 0;
}

No comments:

Post a Comment