Posted in DFS

PKU 15 Red and Black

Problem: http://acmicpc.openjudge.cn/practice/015/


#include<iostream>
#include<cstring>
using namespace std;
string a[25];
bool visited[25][25];
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int w, h; 
int cnt = 0;

bool range(int x, int y) {
	// cout << x << ' ' << y << endl;
	if (x >= 0 && x < h && y >= 0 && y < w) {
		// cout << "true";
		return true;
	} 
	return false;
}

void dfs(int x, int y) {
	// cout << x << ' ' << y << ' ' << a[x][y] << ' ' << visited[x][y] << endl;
	if (range(x, y) && a[x][y] == '.' && !visited[x][y]) {
		// cout << x << ' ' << y << endl;
		cnt ++;
		visited[x][y] = true;	
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			dfs(xx, yy);
		} 			
	}
}

int main() {
	while (cin >> w >> h) {
		if (w == 0 && h == 0) {
			return 0;
		}
		cnt = 0;
		bool end = false;
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < h; i++) {
			cin >> a[i];
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (a[i][j] == '@') {
					// cout << i << ' ' << j << endl;
					a[i][j] = '.';
					dfs(i, j);
					cout << cnt << endl;
					end = true;
					break;
				}
			}
			if (end) {
				break;
			}
		}			
	}
	return 0;
}

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s