广度优先搜索 + 多源最短路径
感悟：这个题啊，其实可以转换个思路，转换成1的格子到其他0的格子的最短路径，就基本知道是多源最短路径的问题。说到多源最短路径有个大名鼎鼎的Floyd算法，不过本题不用这么麻烦，因为读懂题目可知边的权值都是1(相邻边)。可以直接用广搜，等下详细说。还有啊，今天终于报上了心心念念的老师的算法基础课，很激动，尽管自己水平不咋地，还是得加油啊！！！
广搜的基本框架可以看看这篇 广搜框架
本题思路
从1格子开始，往其他地方搜索，走一步距离加一（挺简单的，没啥好说）
- 利用广搜求多源最短路径
- 储存地图g，状态d，都用二维数组
- 开始状态：1格子的地方距离都是0；最终状态：其他地方走到，并记录距离；
- 二维的四个方向
- 每走一步距离+1
pair
pair<int, int> p; //第一个坐标p.first,第二个坐表p.second;
ACcode
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1005;
typedef pair<int, int> pp;
int n, m;
char g[N][N];
int d[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs()
{
memset(d, -1, sizeof d);
queue<pp> q;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(g[i][j] == '1')
{
d[i][j] = 0;
q.push({i, j}); //加入的时候应该将x,y坐标作为一个整体加入
}
while(q.size())
{
auto t = q.front(); q.pop();
int x = t.first, y = t.second;
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny] == -1)
{
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
scanf("%s", g[i]);
bfs();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
printf("%d ", d[i][j]);
printf("\n");
}
return 0;
}
