ACM (UVa) : 572



#include <iostream>
#include <list>
using namespace std;

char a [105] [105];
list <int> var;

void recur ()
{
	int col = var.front ();
	var.pop_front ();
	int row = var.front ();
	var.pop_front ();
	a [row] [col] = '*';

	if (a [row - 1] [col - 1] == '@') { // diagonal top-left
		var.push_front (row - 1);
		var.push_front (col - 1);
	}

	if (a [row -1] [col] == '@') { // up
		var.push_front (row - 1);
		var.push_front (col);
	}

	if (a [row - 1] [col + 1] == '@') { // diagonal top-right
		var.push_front (row - 1);
		var.push_front (col + 1);
	}

	if (a [row] [col + 1] == '@') { // right
		var.push_front (row);
		var.push_front (col + 1);
	}

	if (a [row + 1] [col + 1] == '@') { // diagonal down-right
		var.push_front (row + 1);
		var.push_front (col + 1);
	}

	if (a [row + 1] [col] == '@') { // down
		var.push_front (row + 1);
		var.push_front (col);
	}

	if (a [row + 1] [col - 1] == '@') { // diagonal down-left
		var.push_front (row + 1);
		var.push_front (col - 1);
	}

	if (a [row] [col - 1] == '@') { // left
		var.push_front (row);
		var.push_front (col - 1);
	}
}

int main ()
{
    int m, n;

    while (cin >> m >> n) {

		if (m == 0)
			return 0;

        var.clear ();

        int i, j; // blank
		for (i = 0; i < 105; i++) {
			for (j = 0; j < 105; j++)
				a [i] [j] = '.';
		}
		
		for (i = 1; i <= m; i++) { // input
            for (j = 1; j <= n; j++)
            cin >> a [i] [j];
        }

        int count = 0;
        for (i = 1; i <= m; i++) {
            for (j = 1; j <= n; j++) {
                if (a [i] [j] == '@') {
                    count++;
					var.push_front (i);
                    var.push_front (j);
                    while (var.size ())
						recur ();
                }
            }
        }

		cout << count << endl;
    }

    return 0;
}

Recursive solution

#include <stdio.h>

int m;
int n;
char grid [100 + 5] [100 + 5];
int cnt;

void dfs (int r, int c)
{
    if ( r < 0 || r >= m || c < 0 || c >= n || grid [r] [c] == '*' )
        return;

    grid [r] [c] = '*';

    dfs (r - 1, c); // up
    dfs (r - 1, c + 1); // top-right
    dfs (r, c + 1); // right
    dfs (r + 1, c + 1); // bottom-right
    dfs (r + 1, c); // bottom
    dfs (r + 1, c - 1); // bottom-left
    dfs (r, c - 1); // left
    dfs (r - 1, c - 1); // top-left
}

int main ()
{
    while ( scanf ("%d %d", &m, &n) ) {
        if ( m == 0 && n == 0 )
            break;

        cnt = 0;

        for ( int i = 0; i < m; i++ ) {
            scanf ("%s", grid [i]);
        }

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                if ( grid [i] [j] == '@' ) {
                    cnt++;
                    dfs (i, j);
                }
            }
        }

        printf ("%d\n", cnt);
    }

    return 0;
}

One thought on “ACM (UVa) : 572

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