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