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;
}

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab