AGC 033 A - Darker and Darker

問題概要

A - Darker and Darker
H*W列内に".", "#"が存在する。
存在する#を起点に十字で.を#に置き換える。
上記を繰り返したときに、何回目で全てのマスが埋まるか答えよ。

解法

"."→"#"に置き換えたところをqueueに入れ、幅優先探索で置き換えていけば良い。

提出コード

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define INF 1e9

int mp[1001][1001];
bool used[1001][1001];
int hw_count;
int h, w;

int main()
{
	int first_count = 0;
	cin >> h >> w;
	queue<pair<int,int>> q;
	rep(i, h) {
		string s;
		cin >> s;
		rep(j, w) {
			if (s[j] == '#') {
				mp[i][j] = 1;
				first_count++;
				q.push(make_pair(i,j));
			} else {
				mp[i][j] = 0;
			}
		}
	}
	int count = first_count;
	int ans_count = 0;
	hw_count = h * w;
	if (first_count == hw_count) {
		cout << 0 << endl;
		exit(0);
	}
	while(1) {
		if (count == hw_count || q.empty()) {
			break;
		}
		ans_count++;
		queue<pair<int,int>> q2;
		while(!q.empty()) {
			pair<int,int> qq = q.front();
			int qi = qq.first;
			int qj = qq.second;
			q.pop();
			if (mp[qi][qj] == 1) {
				if (used[qi][qj] == true) {
					continue;
				}
				used[qi][qj] = true;
				if (qi + 1 < h) {
					if (mp[qi + 1][qj] == 0) {
						count++;
						mp[qi + 1][qj] = 1;
						q2.push(make_pair(qi + 1,qj));
					}
				}
				if (qj + 1 < w) {
					if (mp[qi][qj + 1] == 0) {
						count++;
						mp[qi][qj + 1] = 1;
						q2.push(make_pair(qi,qj + 1));
					}
				}
				if (qi - 1 >= 0) {
					if (mp[qi - 1][qj] == 0) {
						count++;
						mp[qi - 1][qj] = 1;
						q2.push(make_pair(qi - 1, qj));
					}
				}
				if (qj - 1 >= 0) {
					if (mp[qi][qj - 1] == 0) {
						count++;
						mp[qi][qj - 1] = 1;
						q2.push(make_pair(qi, qj - 1));
					}
				}	
			}
		}
		q = q2;
	}
	cout << ans_count << endl;
	return 0;
}