超过具有 1 的最近像元的距离的时间限制

Question

给定一个大小为 N x M 的二进制矩阵。任务是找到每个单元格的矩阵中最接近 1 的距离。距离计算公式为 |i1 – i2|+ |j1 – j2|，其中 i1、j1 是当前单元格的行号和列号，i2、j2 是值为 1 的最近单元格的行号和列号。

输入： 输入的第一行是一个整数 T，表示测试用例的数量。然后是 T 测试用例。每个测试用例由 2 行组成。每个测试用例的第一行包含两个整数 M 和 N，表示矩阵的行数和列数。然后在下一行是矩阵 (mat( 的 N*M 空间分隔值。

输出： 对于新行中的每个测试用例，在以空格分隔的单行中打印所需的距离矩阵。

Constraints:
1 <= T <= 20
1 <= N, M <= 500
Example:
Input:
2
2 2 
1 0 0 1
1 2
1 1
Output:
0 1 1 0
0 0

解释：

Testcase 1:
1 0
0 1
0 at {0, 1} and 0 at {1, 0} are at 1 distance from 1s at {0, 0} and {1, 1} respectively.

法典：

bool isSafe(int currRow,int currCol,int n,int m){
return currRow>=0 && currRow<n && currCol>=0 && currCol<m;
}
int bfs(int currX,int currY,vector<int> matrix[],int n,int m) {
queue<pair<int,int>> q;
q.push(make_pair(currX,currY));
static int rows[]={0,-1,0,1};
static int columns[]={1,0,-1,0};
int flag=0;
int dist=0;
while(flag==0 && !q.empty()) {
pair<int,int> p=q.front();
q.pop();
for(int i=0;i<4;i++) {
if(isSafe(p.first+rows[i],p.second+columns[i],n,m)) {
if(matrix[p.first+rows[i]][p.second+columns[i]]) {
dist=abs(p.first+rows[i]-currX)+abs(p.second+columns[i]-currY);
flag=1;
break;
} else {
q.push(make_pair(p.first+rows[i],p.second+columns[i]));
}
}
}
}
return dist;
} 
void minDist(vector<int> matrix[],int n,int m) {
int dist[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(matrix[i][j]) {
dist[i][j]=0;
} else {
dist[i][j]=bfs(i,j,matrix,n,m);
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cout<<dist[i][j]<<" ";
}
}
}
Agorithm:
1. If matrix[i][j] == 1
dist[i][j]=0
else
dist[i][j]= bfs with source as (i,j)

Answer 1

您的算法效率不高，因为每次运行 BFS"仅"会导致一次单元格更新。

您应该从不同的角度解决这个问题，更像是洪水填充：只执行一次BFS 遍历，从队列中具有 1 的所有节点开始。然后，当您扩展到尚未具有已知距离的单元格时，请填写它。

以下是适应该想法的代码：

void minDist(vector<int> matrix[],int n,int m) {
int dist[n][m];
vector<pair<int,int>> q; // in this method, we have enough with vector
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(matrix[i][j]) {
dist[i][j]=0;
q.push_back(make_pair(i,j));
} else {
dist[i][j]=-1; // undefined distance
}
}
}
// bfs
static int rows[]={0,-1,0,1};
static int columns[]={1,0,-1,0};
int curdist=1;
while(!q.empty()) {
vector<pair<int,int>> q2; // use separate vector for the next extension
while(!q.empty()) {
pair<int,int> p=q.back();
q.pop_back();
for(int i=0;i<4;i++) {
if(isSafe(p.first+rows[i],p.second+columns[i],n,m)) {
if(dist[p.first+rows[i]][p.second+columns[i]] == -1) {
dist[p.first+rows[i]][p.second+columns[i]] = curdist;
q2.push_back(make_pair(p.first+rows[i],p.second+columns[i]));
}
}
}
}
q = q2; // Now copy that extension back into the original vector
curdist++;
}
// output
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cout<<dist[i][j]<<" ";
}
cout<<"n";
}
}