AcWing 728. 变身程序员
原题链接
中等
作者:
王小强
,
2021-01-26 16:41:29
,
所有人可见
,
阅读 307
BFS
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
static constexpr int dirs[] { 0, -1, 0, 1, 0 };
const int N = 15;
int g[N][N];
int main() {
int m = 0, n = 0;
string line;
while (getline(cin, line)) {
int j = 0;
stringstream in(line);
while (in >> g[m][j]) ++j;
n = j, ++m;
}
queue<P> q;
int pms = 0; // PM 的数量
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x)
if (g[y][x] == 1) ++pms; // 1 == PM
else if (g[y][x] == 2) q.emplace(x, y); // 把所有程序员们先入队
int minutes = 0;
while (not q.empty() && pms) {
size_t sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == n || ny == m || g[ny][nx] != 1)
continue;
g[ny][nx] = 2; // 把产品经理变成程序员
--pms; // PM 团队减员1个单位
q.emplace(nx, ny);
}
}
++minutes;
}
cout << (pms ? -1 : minutes) << endl;
return 0;
}