二元矩阵中最近的1-yiteyi-C++库

给定一个m*n阶的二进制矩阵，任务是为矩阵中的每一个0找到最接近1的距离，并打印最终的距离矩阵。从任何一个单元（i，j），我们只能向上、下、左、右四个方向移动。注：从一个单元格到另一个单元格的距离总是增加1。 例如：

null

Input : m = 3, n = 4        mat[m][n] = {{0, 0, 0, 1},                     {0, 0, 1, 1},                     {0, 1, 1, 0}}Output: 3 2 1 0        2 1 0 0        1 0 0 1

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 对于这个问题，需要对矩阵中的每个0递归检查矩阵中最近的1。一 有效解决方案 解决这个问题的方法是使用 BFS .以下是解决此问题的算法：

取距离矩阵dist[m][n]并用INT_MAX初始化它。
现在遍历矩阵，使单元（i，j）的索引的_对（i，j）具有值“1”，并将该对推入队列并更新dist[i][j]=0，因为“1”与自身的距离将始终为0。
现在逐个弹出队列中的元素，直到它变空并调用 BFS 在上面。
在这里，我们需要找到最近的一个的距离，我们正在呼叫 BFS 对于具有“1”的单元，因此每当我们从队列中获取弹出元素的相邻部分时，我们都会通过设置条件if（dist[i][j]+1） BFS 遍历并填充完整的距离矩阵。
在完成 BFS 遍历距离矩阵的每个单元格将包含最近的“1”的距离。

C++

                         // C++ program to find the minimum distance from a                       
                         // "1" in binary matrix.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         const                                     int                                     MAX = 1000;                       
           
                         // distance matrix which stores the distance of                       
                         // nearest '1'                       
                         int                                     dist[MAX][MAX];                       
           
                         // Function to find the nearest '1'                       
                         void                                     nearestOne(                                     int                                     mat[][MAX],                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 // two array when respective values of newx and                       
                                                 // newy are added to (i,j) it gives up, down,                       
                                                 // left or right adjacent of (i,j) cell                       
                                                 int                                     newx[] = {-1, 0, 1, 0};                       
                                                 int                                     newy[] = {0, -1, 0, 1};                       
           
                                                 // queue of pairs to store nodes for bfs                       
                                                 queue< pair<                                     int                                     ,                                     int                                     > > q;                       
           
                                                 // traverse matrix and make pair of indices of                       
                                                 // cell (i,j) having value '1' and push them                       
                                                 // in queue                       
                                                 for                                     (                                     int                                     i=0; i<m; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=0; j<n; j++)                       
                                                 {                       
                                                 dist[i][j] = INT_MAX;                       
           
                                                 if                                     (mat[i][j] == 1)                       
                                                 {                       
                                                 // distance of '1' from itself is always 0                       
                                                 dist[i][j] = 0;                       
           
                                                 // make pair and push it in queue                       
                                                 q.push(make_pair(i, j));                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // now do bfs traversal                       
                                                 // pop element from queue one by one until it gets empty                       
                                                 // pair element to hold the currently popped element                       
                                                 pair<                                     int                                     ,                                     int                                     > poped;                       
                                                 while                                     (!q.empty())                       
                                                 {                       
                                                 poped = q.front();                       
                                                 q.pop();                       
           
                                                 // coordinate of currently popped node                       
                                                 int                                     x = poped.first;                       
                                                 int                                     y = poped.second;                       
           
                                                 // now check for all adjancent of popped element                       
                                                 for                                     (                                     int                                     i=0; i<4; i++)                       
                                                 {                       
                                                 int                                     adjx = x + newx[i];                       
                                                 int                                     adjy = y + newy[i];                       
           
                                                 // if new coordinates are within boundary and                       
                                                 // we can minimize the distance of adjacent                       
                                                 // then update the distance of adjacent in                       
                                                 // distance matrix and push this adjacent                       
                                                 // element in queue for further bfs                       
                                                 if                                     (adjx>=0 && adjx<m && adjy>=0 && adjy<n &&                       
                                                 dist[adjx][adjy] > dist[x][y] + 1)                       
                                                 {                       
                                                 // update distance                       
                                                 dist[adjx][adjy] = dist[x][y] + 1;                       
                                                 q.push(make_pair(adjx,adjy));                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver program to run the case                       
                         int                                     main()                       
                         {                       
                                                 int                                     m = 3, n = 4;                       
                                                 int                                     mat[][MAX] = {{0, 0, 0, 1},                       
                                                 {0, 0, 1, 1},                       
                                                 {0, 1, 1, 0}                       
                                                 };                       
                                   
                                                 // Fills values in dist[][]                       
                                                 nearestOne(mat, m, n);                       
           
                                                 // print distance matrix                       
                                                 for                                     (                                     int                                     i=0; i<m; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=0; j<n; j++)                       
                                                 cout << dist[i][j] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                                                 }                       
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 program to find the minimum distance from a                       
                         # "1" in binary matrix.                       
                         MAX                                     =                                     1000                       
                         INT_MAX                                     =                                     (                                     2                                     *                                     *                                     32                                     )                       
           
                         # distance matrix which stores the distance of                       
                         # nearest '1'                       
                         dist                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (                                     MAX                                     )]                                     for                                     j                                     in                                     range                                     (                                     MAX                                     )]                       
           
                         # Function to find the nearest '1'                       
                         def                                     nearestOne(mat, m, n):                       
                                   
                                                 # two array when respective values of newx and                       
                                                 # newy are added to (i,j) it gives up, down,                       
                                                 # left or right adjacent of (i,j) cell                       
                                                 newx                                     =                                     [                                     -                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ]                       
                                                 newy                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     0                                     ,                                     1                                     ]                       
                                   
                                                 # queue of pairs to store nodes for bfs                       
                                                 q                                     =                                     []                       
                                   
                                                 # traverse matrix and make pair of indices of                       
                                                 # cell (i,j) having value '1' and push them                       
                                                 # in queue                       
                                                 for                                     i                                     in                                     range                                     (m):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 dist[i][j]                                     =                                     INT_MAX                       
                                                 if                                     (mat[i][j]                                     =                                     =                                     1                                     ):                       
                                   
                                                 # distance of '1' from itself is always 0                       
                                                 dist[i][j]                                     =                                     0                       
                                   
                                                 # make pair and push it in queue                       
                                                 q.append([i, j])                       
                                   
                                                 # now do bfs traversal                       
                                                 # pop element from queue one by one until it gets empty                       
                                                 # pair element to hold the currently popped element                       
                                                 poped                                     =                                     []                       
                                                 while                                     (                                     len                                     (q)):                       
                                                 poped                                     =                                     q[                                     0                                     ]                       
                                                 q.pop(                                     0                                     )                       
                                   
                                                 # coordinate of currently popped node                       
                                                 x                                     =                                     poped[                                     0                                     ]                       
                                                 y                                     =                                     poped[                                     1                                     ]                       
                                   
                                                 # now check for all adjancent of popped element                       
                                                 for                                     i                                     in                                     range                                     (                                     4                                     ):                       
                                   
                                                 adjx                                     =                                     x                                     +                                     newx[i]                       
                                                 adjy                                     =                                     y                                     +                                     newy[i]                       
                                   
                                                 # if new coordinates are within boundary and                       
                                                 # we can minimize the distance of adjacent                       
                                                 # then update the distance of adjacent in                       
                                                 # distance matrix and push this adjacent                       
                                                 # element in queue for further bfs                       
                                                 if                                     (adjx >                                     =                                     0                                     and                                     adjx < m                                     and                                     adjy >                                     =                                     0                                     and                       
                                                 adjy < n                                     and                                     dist[adjx][adjy] > dist[x][y]                                     +                                     1                                     ):                       
                                   
                                                 # update distance                       
                                                 dist[adjx][adjy]                                     =                                     dist[x][y]                                     +                                     1                       
                                                 q.append([adjx, adjy])                       
           
                         # Driver code                       
                         m                                     =                                     3                       
                         n                                     =                                     4                       
                         mat                                     =                                     [[                                     0                                     ,                                     0                                     ,                                     0                                     ,                                     1                                     ], [                                     0                                     ,                                     0                                     ,                                     1                                     ,                                     1                                     ], [                                     0                                     ,                                     1                                     ,                                     1                                     ,                                     0                                     ]]                       
           
                         # Fills values in dist[][]                       
                         nearestOne(mat, m, n)                       
           
                         # print distance matrix                       
                         for                                     i                                     in                                     range                                     (m):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 print                                     (dist[i][j], end                                     =                                     " "                                     )                       
                                                 print                                     ()                       
           
                         # This code is contributed by shubhamsingh10                       

输出：

3 2 1 02 1 0 01 0 0 1

本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章