矩阵距离（多源BFS）

蔚落 2022-10-26 12:56 106阅读 0赞

**题目描述**  
给定一个N行M列的01矩阵A，A\[i\]\[j\] 与 A\[k\]\[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])

**输入格式**  
第一行两个整数n,m。

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

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

**数据范围**  
1≤N,M≤1000  
**输入样例：**

3 4
    0001
    0011
    0110

**输出样例：**

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

思路：本题是求0的位置距离所有1的最短的曼哈顿距离。

求一个点到**多个起点**的最短距离，可以给所有起点加一个虚拟点（与起点距离为0），这样就把题目转化成求这个点到虚拟点的最短距离。

本题仅需把所有1节点入队，并把距离置为0，转化成跑单源bfs。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f3f;
    ll n,m;
    struct node{ 
    	ll x,y;
    };
    char mp[1005][1005];
    ll dis[1005][1005];
    ll dx[4]={ -1,1,0,0};
    ll dy[4]={ 0,0,-1,1};
    queue<node> q;
    void dfs()
    { 
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{ 
    			if(mp[i][j]=='1')
    			{ 
    				dis[i][j]=0;
    				q.push({ i,j});
    			}
    		}
    	while(!q.empty())
    	{ 
    		node temp=q.front();
    		q.pop();
    		for(int i=0;i<4;i++)
    		{ 
    			ll x=temp.x+dx[i];
    			ll y=temp.y+dy[i];
    			if(x<0||y<0||x>=n||y>=m) continue;
    			if(dis[x][y]!=-1) continue;
    			dis[x][y]=dis[temp.x][temp.y]+1;
    			q.push({ x,y}); 
    			
    		}
    	}	 
     
    }
    int main()
    { 
    	memset(dis,-1,sizeof(dis));
    	cin>>n>>m;
    	for(int i=0;i<n;i++) cin>>mp[i];
    	dfs();
    	for(int i=0;i<n;i++)
    	{ 
    		for(int j=0;j<m;j++)
    			cout<<dis[i][j]<<" ";
    		cout<<endl;
    	} 
    	return 0;
    }