矩阵距离（搜索与图论、bfs）

给定一个 n×mn×m 的 0101 矩阵：

a11 a12 ... a1m
...
an1 an2 ... anm

定义 aijaij 与 aklakl 之间的距离为 D(aij,akl)=|i−k|+|j−l|。

对于每个元素 aij，请求出与它距离最近且值为 1 的元素 aklakl 和它的距离是多少。

另外注意，当元素 aijaij 本身就为 1 时，与它距离最近且值为 1 的元素就是它自己，距离为 0。

输入格式

第一行为两个整数，分别代表 n 和 m。

接下来的 n 行，第 i 行的第 j 个字符代表 aij。

输出格式

共 n 行，第 i 行的第 j 个数字表示 aij 与其距离最近且值为 1 的元素的距离。

数据范围

1≤n,m≤1000

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

bfs起点太多可以考虑从终点开始bfs，题目要找最近的1，我们可以让1去找零 

#include<bits/stdc++.h>
using namespace std; using ll = long long;
int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
//using lll = __int128; template <class T> istream& read(T& x, istream& cin = std::cin) { T num = 0; bool f = 0; char ch = 0; while (!isdigit(ch)) { f |= ch == '-'; if (!cin.get(ch)) return cin; }while (isdigit(ch)) { num = (num << 3) + (num << 1) + (ch ^ 48); if (!cin.get(ch)) break; }x = f ? -num : num; return cin; }template <class T> ostream& write(T x, ostream& cout = std::cout) { if (x < 0) cout.put('-'), x = -x; if (x > 9) write(x / 10); cout.put(x % 10 + '0'); return cout; }ostream& operator<<(ostream& cout, lll x) { write(x); return cout; }istream& operator>>(istream& cin, lll& x) { return read(x); }bool check(int i, int j);
bool check(int i, int j);

const int N = 1e3 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m;
char g[N][N];
int d[N][N];

using pii = pair<int, int>;
queue<pii> qu;
bool st[N][N];

void init() {
	memset(d, 0x3f, sizeof d);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> g[i][j];
			if (g[i][j] == '1') {
				qu.emplace(i, j);
				d[i][j] = 0;
				st[i][j] = 1;
			}
		}
	}
	return;
}

void bfs() {
	while (qu.size()) {
		auto [x, y] = qu.front();
		//cout << x << " " << y << endl;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0], ny = y + dir[i][1];
			if (!nx || !ny || nx > n || ny > m || st[nx][ny]) continue;
			st[nx][ny] = 1;
			d[nx][ny] = d[x][y] + 1;
			qu.emplace(nx, ny);
		}
	}
	return;
}

void solve() {
	bfs();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << d[i][j] << " ";
		}
		cout << "\n";
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(6) << fixed;
	int TT = 1;
	//cin >> TT;
	for (int ii = 1; ii <= TT; init(), solve(), ii++) {}
	return 0;
}