UVa: 785 (Grid Colouring)



http://uva.onlinejudge.org/external/7/785.html
Time: 0.069s
Tag: DFS, IO

#include <cstdio>
#include <cstring>

using namespace std;

char matrix [30 + 5] [80 + 5];

char mark;

int dr[] = {1, 0, -1, 0}; // up, right, down, left
int dc[] = {0, 1, 0, -1};

int line;

bool isValid(int x, int y) {
    // we are in contours, so don't bother to check for matrix boundary cases
    if (matrix [x] [y] == mark || matrix [x] [y] == 'X') return false;
    return true;
}

void dfs (int x, int y) {

    for ( int i = 0; i < 4; i++ ) {
        int nx = x + dr [i];
        int ny = y + dc [i];
        if (isValid(nx, ny)) {

            matrix [nx] [ny] = mark;
            dfs(nx, ny);
        }
    }
}

int main ()
{
    while (gets (matrix [0])) {
        line = 1;

        while (gets (matrix [line])) {
            if (matrix [line] [0] == '_') break;
            line++;
        }

        for ( int i = 0; i < line; i++ ) {
            for ( int j = 0; j < strlen (matrix [i]); j++ ) {
                // we are looking for non-contours char
                if ( matrix [i] [j] != ' ' && matrix [i] [j] != 'X' ) {
                    mark = matrix [i] [j];
                    matrix [i] [j] = ' ';
                    dfs(i, j);

                    // revert the changes to original
                    matrix [i] [j] = mark;
                }
            }
        }

        for ( int i = 0; i <= line; i++ ) {
            printf ("%s\n", matrix [i]);
        }
    }

    return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s