题目描述

blablabla

思路

图的BFS，矩阵类型的BFS，与链表类型区分

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
int n,m;
int a[N][N],d[N][N];
bool st[N][N];
queue<PII> q;

void bfs(){
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i = 0;i < 4;i++){
            int x = t.first + dx[i],y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && st[x][y] != true){
                // 注意理解一个点：每次加距离都是从最靠近的1的位置，也就是d值为0的位置开始算的，不是每次都从初始位置
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x,y});
                st[x][y] = true;
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            // scanf("%d",&a[i][j]);
            // 注意输入为字符
            char c;
            cin>>c;
            a[i][j] = c - '0';
            if(a[i][j] == 1){
                // 把为1的加入队列
                st[i][j] = true;
                q.push({i,j});
            }
        }
    }

    bfs();

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            printf("%d ",d[i][j]);
        }
        puts("");
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla