AcWing 173. 矩阵距离:为什么用char不用int
原题链接
简单
作者:
popomo
,
2024-04-02 22:58:59
,
所有人可见
,
阅读 2
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010, M = 1010;
struct Node{
int x, y;
};
int dis[N][M]; //存结果,判重
int n, m;
char g[N][M]; //为什么用char:
//题目告知了数字之间没有空格,等价于说需要用字符串读入。用 int 读等价于每次读一行,把一行当做一个整数
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(int x, int y)
{
memset(dis, -1, sizeof dis); //为距离数组赋初值为-1
queue<Node> q;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (g[i][j] == '1') //如果是初始点,将该点距离(该点到初始点的距离)赋为1,把初始点全部压入队列
{
dis[i][j] = 0;
q.push({i, j});
}
while(q.size()) //当队列中有坐标点
{
auto u = q.front(); //弹出,取出队列中第一个坐标点
q.pop();
for (int i = 0; i < 4; i ++) //i < 4对应上下左右四个方向的尝试
{
int a = u.x + dx[i], b = u.y + dy[i]; //尝试的点的坐标(a, b)
if (a < 0 || a >= n || b < 0 || b >= m) continue; //出界
if (dis[a][b] != -1) continue; //距离不为-1,即不是新的点,之前走过了
//思路是从距离为0的点,到距离为1的点,再到距离为2的点,每次+1来形成最后结果的距离数组
dis[a][b] = dis[u.x][u.y] + 1; //该点(子节点)的距离标记为它的父节点 + 1
q.push({a, b}); //将新节点压入队列
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
cin >> g[i][j];
bfs(0, 0);
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
cout << dis[i][j] << ' ';
cout << endl;
}
return 0;
}