最近上课的时候，老师给我们布置了七道题，目前做出来六道（果然是我太蒻了），准备一一做点记录。
文章目录
题目描述
不要想链接了，找不到的
题目描述
给定一个 \( N \) 行 \( M \) 列的01矩阵 \( A \)，\( A\left[i\right]\left[j\right] \) 与 \( A\left[k\right]\left[l\right] \) 之间的曼哈顿距离定义为：\( dist\left(A\left[i\right]\left[j\right] , A\left[k\right]\left[l\right]\right) = \left\vert i – k\right\vert + \left\vert j – l\right\vert \)
输出一个 \( N \) 行 \( M \) 列的整数矩阵 \( B \)，其中：\( B\left[i\right]\left[j\right] = \min\{dist\left(A\left[i\right]\left[j\right] , A\left[x\right]\left[y\right]\right)\} , 1\leq x \leq N , 1 \leq y \leq M , A\left[x\right]\left[y\right] = 1 \)
输入格式
第一行两个整数n，m。
接下来一个 \( N \) 行 \( M \) 列的01矩阵，数字之间没有空格。
输出格式
一个 \( N \) 行 \( M \) 列的矩阵 \( B \)，相邻两个整数之间用一个空格隔开。
输入输出样例
输入 #1
3 4 0001 0011 0110
输出 #1
3 2 1 0 2 1 0 0 1 0 0 1
说明/提示
[数据规模] \( 1 \leq N, M \leq 1000 \)
知识链接
曼哈顿距离
曼哈顿距离（也被称为“出租车距离”）是什么东西呢？其实，它就是指坐标系上两个点的一种距离。我们先看一下它和传统的欧几里得距离（欧氏距离）对两个点 \( A\left( x_1, y_1\right) , B\left( x_2, y_2\right) \) 的计算公式：
$$
D_M\left(A, B\right) = \left\vert x_1 – x_2\right\vert + \left\vert y_1 – y_2\right\vert\\
D_E\left(A, B\right) = \sqrt{\left( x_1 – x_2\right)^2 + \left( y_1 – y_2\right)^2 }
$$
其中 \( D_M \) 是曼哈顿距离，\( D_E \) 是欧氏距离，通过公式可知曼哈顿距离比欧氏距离少了一个根号运算和两个平方运算，在计算机中能够获得更高的精度和更快的运算速度，这也是曼哈顿距离的优势，在之前的“洛谷刷题记——P1379 八数码难题（BFS A* 实现）”这篇文章中我们也提到过曼哈顿距离。
解题思路
这道题其实非常简单，难就难在两个点：一个是对题意的分析理解，另一个是输入输出。
题意分析
我们仔细看一下题目，看完之后我们肯定能很简单地理解矩阵 \( A \) 是怎么回事，但这个 \( B \) 怎么求的，这是比较费解的。其实，我们完全可以用一种通俗的语言来描述：
给定一个01矩阵，求这个矩阵中每个位置的数到离它最近的“1”的曼哈顿距离
这样，我们就将晦涩的题目转化为了简单的图论模板题。
解题过程
我们解决了题意问题，那我们该怎么解决这个问题呢？
暴力方法
我们首先考虑暴力方法。看到这题后我先有一个思路：预先算出所有点之间的曼哈顿距离，然后再枚举每个点跟所有为“1”的点的距离，取其中最小值就是这个点的值。然而，这样的方法肯定是不行的，因为这样做的复杂度是 \( O\left(nm\left(nm – 1\right)\right) \approx O\left(n^2m^2\right) \)，这种复杂度在这道题的数据范围中肯定是会超时的。我们有一种优化思路：把所有为“1”的点都记录一下位置，然后枚举距离时只用在这些为“1”的点中枚举即可，这样做的复杂度是 \( O\left( \frac{nm\left( nm – 1\right) }{2} + nmp\right) \approx O\left( n^2m^2\right) \)，其中 \( p \) 为“1”的个数。
然而我们可以发现，这样做的复杂度并没有太大的优化。通过仔细分析可以发现：时间的耗费主要是耗费在计算所有点之间的曼哈顿距离上了。然后我又有了一种思路：其实没有必要计算那么多无用的距离，我们只要从每个点出发，找到所有为“1”的点，在这时候算出它们之间的曼哈顿距离，这样做的复杂度为 \( O\left( nmp\right) \)，相对于上面方法已经有了很大的优化，在 \( p \) 不大的时候应该是可以水过这道题的，但显然我们老师出数据时满满的恶意，六个点T了三个，令我非常懵。而且，如果在极限状况下，复杂度有可能退化为近似 \( O\left(n^2m^2\right) \)，所以我们显然需要更好的算法。
正解
那么正解究竟是什么呢？答：BFS。看到这里，小朋友，你是否有很多问号？？？BFS不也是暴力方法之一吗？如果你产生了这样的想法（没有的话当我没说），那就说明你混淆了一个重要的概念：搜索是一种算法，而暴力方法是一种算法思想。遵循暴力方法写的搜索叫做暴搜，而搜索显然还有其他优化的方法。在本题中，我们可以使用一种非常简单的方法：从每个“1”点开始搜索，由于BFS的特性，搜到这个点所经过的路径长度显然就是这个“1”点到达这个点最短的路径；另外，由于BFS的特性，如果这个点还没有被其他的“1”点搜索过，那么显然离这个点最近的“1”点就是当前的这个“1”点。这样做，我们只需要将所有的点遍历一遍就可以得出最终结果，复杂度大约为 \( O\left(nm\right) \)，应该是本题最好的做法了。
理清了这一思路，我们就可以很轻松地写出代码了。另外，输入方面它是中间没有空格的，用普通的scanf输入肯定是非常麻烦的，我们可以使用一种简化版的快读进行输入。
代码展示
拒绝抄袭，共创和谐社会[机智]
#include <cstdio> // std::scanf, std::getchar, std::printf, std::putchar
#include <cstring> // std::memset
#include <cctype> // std::isdigit
#include <queue> // std::queue
#include <utility> // std::pair
using namespace std;
const int kMaxN(1000);
int kB[kMaxN + 5][kMaxN + 5]; // 只存B矩阵，A矩阵不用储存
int kXMov[5] = {0, -1, 0, 1}; // 方便坐标移动
int kYMov[5] = {1, 0, -1, 0};
queue<pair<int, int> > kQueue; // BFS遍历，要存坐标，懒得写结构体，就用了C++自带的pair
void Bfs(int, int); // BFS遍历
inline bool IsValid(int, int, int, int); // 判断当前坐标是否合法
int main(void) {
int n(0), m(0);
memset(kB, -1, sizeof(kB)); // 没访问过的点设为-1，这样就不用另外开一个数组来记录是否访问过了
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char ch(getchar());
while (!isdigit(ch)) // 如果当前字符不是数字
ch = getchar(); // 继续读
if (ch - '0') { // 如果这个数是1
kB[i][j] = 0; // 距离自然就是0了
kQueue.push(make_pair(i, j)); // 加入队列
}
}
}
Bfs(n, m); // 开始BFS
// 输出
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
printf("%d", kB[i][j]);
if (j != m - 1)
putchar(' ');
}
putchar('\n');
}
return 0;
}
void Bfs(int n, int m) {
pair<int, int> now;
while (!kQueue.empty()) {
now = kQueue.front(); // 取出要处理的点
kQueue.pop();
for (int i = 0; i < 4; ++i) {
int dx(now.first + kXMov[i]), dy(now.second + kYMov[i]); // 向四个方向移动
if (IsValid(n, m, dx, dy) && -1 == kB[dx][dy]) { // 如新坐标是合法的
kB[dx][dy] = kB[now.first][now.second] + 1; // 距离=当前点距离＋1，一种计算曼哈顿距离的取巧方法
kQueue.push(make_pair(dx, dy)); // 将新坐标加入队列
}
}
}
}
inline bool IsValid(int n, int m, int dx, int dy) {
if (-1 < dx && dx < n && -1 < dy && dy < m) // 没有越界
return true;
else
return false;
}
写在最后
这题应该是非常之简单的，但我竟然没有第一时间想出来，实在是做题经验不够，写下这篇博客警醒一下自己，希望以后不要再犯这样的错误。