给定一个N行M列的01矩阵A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：

 

dist(A[i][j],A[k][l])=|i−k|+|j−l|dist(A[i][j],A[k][l])=|i−k|+|j−l|

 

输出一个N行M列的整数矩阵B，其中：

 

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1⁡dist(A[i][j],A[x][y])

 

输入格式

第一行两个整数n,m。

接下来一个N行M列的01矩阵，数字之间没有空格。

输出格式

一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤10001≤N,M≤1000

输入样例：

3 4000100110110

输出样例：

3 2 1 02 1 0 01 0 0 1

 

算法：bfs

题意：就是给你一个矩阵，然后矩阵里面有很多初始点，你需要求这些初始点到矩阵其他位置的最小距离。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 1e3+7;int n, m;int Map[maxn][maxn];int step[maxn][maxn];int dir[4][2] = {
   0, -1, 0, 1, -1, 0, 1, 0};bool check(pair
        
          next) {    if(next.first <= 0 || next.first > n || next.second <= 0 || next.second > m) {        return false;    }     if(step[next.first][next.second] != -1) {        return false;    }    return true;}void bfs() {    queue
         
          
            > q; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(Map[i][j] == 1) { q.push(make_pair(i, j)); step[i][j] = 0; } else { step[i][j] = -1; } } } while(!q.empty()) { pair
           
             now = q.front(); q.pop(); for(int i = 0; i < 4; i++) { pair
            
              next; next.first = now.first + dir[i][0]; next.second = now.second + dir[i][1]; if(check(next)) { step[next.first][next.second] = step[now.first][now.second] + 1; q.push(next); } } }}int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%1d", &Map[i][j]); } } bfs(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { printf("%d%c", step[i][j], " \n"[j == m]); } } return 0; }