网站设计案例网站,网站智能建设系统源码,wordpress 文章内容,网页毕业设计作品题目链接#xff1a;矩阵中的距离
题目#xff1a;
输入一个由 0、1 组成的矩阵 M#xff0c;请输出一个大小相同的矩阵 D#xff0c;矩阵 D 中的每个格子是矩阵 M 中对应格子离最近的 0 的距离。水平或竖直方向相邻的两个格子的距离为 1。假设矩阵 M 中至少有一个 0。
…题目链接矩阵中的距离
题目
输入一个由 0、1 组成的矩阵 M请输出一个大小相同的矩阵 D矩阵 D 中的每个格子是矩阵 M 中对应格子离最近的 0 的距离。水平或竖直方向相邻的两个格子的距离为 1。假设矩阵 M 中至少有一个 0。
例如下图 (a) 是一个只包含 0、1 的矩阵 M它的每个格子离最近的 0 的距离如下图 (b) 的矩阵 D 所示。M[0][0] 等于 0因此它离最近的 0 的距离是 0所以 D[0][0] 等于 0。M[2][1] 等于 1离它最近的 0 的坐标是 (0, 1)、(1, 0)、(1, 2)它们离坐标 (2, 1) 的距离都是 2所以 D[2][1] 等于 2。 分析
应用与图相关的算法解决问题的前提是能够找出图中的节点和边。这是一个背景为矩阵的问题矩阵中的每个格子可以看成图中的一个节点矩阵中上、下、左、右相邻的格子对应的节点之间有一条边相连。例如可以将上图 (a) 中的矩阵看成下图所示的图。 这个题目要求计算每个格子离最近的 0 的距离。根据题目的要求上、下、左、右相邻的两个格子的距离为 1。可以将图看成一个无权图图中两个节点的距离是连通它们的路径经过的边的数目。由于这个问题与无权图的最近距离相关因此可以考虑应用广度优先搜索解决。
广度优先搜索需要一个队列。图中的哪些节点可以当作初始节点添加到队列中这个问题是求每个格子离最近的 0 的距离因此可以将所有的 0 当作初始节点添加到队列中然后以值为 0 的节点作为起点做广度优先搜索。当经过 d 步到达某个格子那么该格子离最近的 0 的距离就是 d。
class Solution {
public:vectorvectorint updateMatrix(vectorvectorint mat) {int rows mat.size(), cols mat[0].size();vectorvectorint dists(rows, vectorint(cols));
queuevectorint q;for (int i 0; i rows; i){for (int j 0; j cols; j){if (mat[i][j] 0){dists[i][j] 0;q.push(vectorint{ i, j });}else{dists[i][j] INT_MAX;}}}
vectorvectorint dirs { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };while (!q.empty()){vectorint coord q.front();q.pop();int dist dists[coord[0]][coord[1]];
for (vectorint dir : dirs){int r coord[0] dir[0];int c coord[1] dir[1];if (r 0 r rows c 0 c cols){if (dists[r][c] dist 1){dists[r][c] dist 1;q.push(vectorint{ r, c });}}}}return dists;}
}; 上述代码创建了一个大小与输入矩阵 mat 相同的二维数组 dists用来记录每个格子离最近的 0 的距离。如果 mat[i][j] 为 0那么这个格子离最近的 0 的距离自然是 0因此 dists[i][j] 设为 0。如果 mat[i][j] 的值为 1则先用最大的整数值初始化 dists[i][j]接下来搜索到对应的节点时再更新它的值。 队列中的元素是矩阵中格子的坐标是一个长度为 2 的数组。一个格子的坐标被添加到队列中之前它离最近的 0 的距离已经计算好并且保存在数组 dists 中。 每次从队列中取出一个坐标为 coord 的格子该格子离最近的 0 的距离用变量 dist 表示。从该格子出发沿着上、下、左、右到达坐标为 (r, c) 的格子。如果该格子之前没有到达过此时 dists[r][c] 的值仍然为最大的整数值那么 dists[r][c] dist 1 的值为 true。由于是从离最近的 0 的距离为 dist 的格子多走一步到达该格子的因此该格子离最近的 0 的距离是 dist 1。此外还需要将该格子添加到队列中以便接下来搜索与该格子相连的其他节点。 如果之前已经到达坐标为 (r, c) 的格子那么 dist[r][c] 的值一定不可能大于 dist 1。这是因为用的是广度优先搜索而广度优先搜索能够保证从起始节点到达任意节点一定是沿着最短路径的。当第 1 次到达坐标为 (r, c) 的格子时记录到 dists[r][c] 的值一定是从值为 0 的格子到达该格子的最短距离。因此当再次到达坐标为 (r, c) 的格子时dists[r][c] dist 1 的值为 false。通过比较距离可以避免重复访问某个格子。
