AcWing 728. 变身程序员
原题链接
中等
作者:
跟着灿哥学切菜
,
2021-02-08 20:27:27
,
所有人可见
,
阅读 331
#include <iostream>
#include <queue>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 15;
typedef pair<int, int> PII;
int n, m;
int dist[N][N];
//g二维数组来记录输入的数组
int g[N][N];
int bfs(){
queue<PII> que;
//首先将dist数组中的所有的位置上的值初始化为-1
memset(dist, -1, sizeof dist);
//将所有的起点全部插入到队列当中
//首先得要来找到所有的起点
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
if (g[i][j] == 2) {
//如果此时这个位置上的数为2, 表示的是这个数是起点
//如果是起点,此时这个位置上的距离源点的是0
dist[i][j] = 0;
que.push({i, j});
}
}
}
//分别表示的是4个方向的偏移量。
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//下面开始整个的bfs的过程
while (que.size()) {
//每一次取出来队头元素
auto t = que.front();
que.pop();
int x = t.first, y = t.second, d = dist[x][y];
for (int i = 0; i < 4; i ++) {
//此时来得到相应的坐标
int a = x + dx[i], b = y + dy[i];
//此时dist[a][b] == -1表示的是此时的这个点还没有扩展到
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 1 && dist[a][b] == -1) {
dist[a][b] = d + 1;
que.push({a, b});
}
}
}
//来查看相应的位置上的距离的最大值
int res = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
if (g[i][j] == 1) {
if (dist[i][j] == -1) return -1;
res = max(res, dist[i][j]);
}
}
}
return res;
}
//此时的输入的矩阵的具体的形态是不知道的, 需要自己来进行计算
//所以此时来使用c++中的流式读取
int main() {
string line;
while (getline(cin, line)) {
int k = 0;
stringstream ssin(line);
while (ssin >> g[n][k]) k ++;
m = k;
n ++;
}
cout << bfs() << endl;
return 0;
}