题意

从1BFS

代码

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	int x,y;//存储坐标的结构体
};
int n,m;
bool a[1145][1145];//输入的0,1的二维数组
int b[1145][1145];//储存距离
bool vis[1145][1145];//标记数组
int xl[4]={-1,1,0,0};//x方位数组
int yl[4]={0,0,-1,1};//y方位数组
void bfs()
{
	queue<node >q;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]==1)
			{
				q.push({i,j});//加进要BFS的队列里
			}
		}
	}
	while(q.size())
	{
		node u=q.front();
		for(int i=0;i<4;i++)
		{
			int x=u.x+xl[i];
			int y=u.y+yl[i];
			if(a[x][y]==0 && x>=0 && x<n && y>=0 && y<m && !vis[x][y] && b[x][y]==0)//有点长
			{
				vis[x][y]=1;//标记
				b[x][y]=b[u.x][u.y]+1;//距离
				q.push({x,y});
			}
		}
		q.pop();//不要忘了
	}
}
int main()
{
	cin>>n>>m;//输入
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			char cs;
			cin>>cs;
			a[i][j]=(cs=='0'?0:1);//样例为什么没有空格,烦啊
		}
	}
	bfs();//BFS
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cout<<b[i][j]<<" ";//输出
		}
		cout<<endl;
	}
	return 0;//完结散花
}

一道帮助理解BFS特征的好题

这是一道非常好的题目，认真理解的话可以真正学好BFS。

1. 考察搜索方向。一般思维是从 A[0][0] 开始往周围扩散，这样的暴力做法时间复杂度为 $O(n^3)$，结合数据范围可发现一定会TLE。那么反过来呢？从值为 $1$ 的 $A$ 元素开始搜索，你自己算一下时间复杂度会不会下降，会降到多少。结论：有时候，把搜索方向反过来，会大大降低时间复杂度，或编码难度。（提示：DP经典例题“数字三角形”，从下往上和从上往下做都可以，但思路和代码复杂度有差别。）
2. 考察对BFS搜索过程特点的深入理解：
   • BFS的辅助队列里，任何时刻最多都只会有两个层次的结点；
   • 从某个点开始BFS，最先扫到的点一定是距起点最近的点。那么从多个起点 $\{s_i\}$ 同时开始BFS的话，若某个点 $P$ 最先被起点 $s_k$ 扫到，那么距离点 $P$ 最近的起点一定是 $s_k$。

做法：把 $A$ 中所有值为 1 的点入队，开始BFS。那么任何时刻队列中最多只有两层结点，保证了每扩展一次结点，都是同时扩展了队列里当前所有最“老”的点的下一层结点。

在BFS过程中，若某个点 $P$ 是第一次被访问，说明点 $P$ 一定离当前的父节点最近，就应该把点 $P$ 对应的 $B$ 的元素 B[P.x][P.y] 填上父节点的层次值+1。

PS：pair 类型的用法之前讲过，忘了的请自己查。

#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int maxn=1010;
const int maxm=1010;
int n,m;
int a[maxn][maxm],b[maxn][maxm];
int dx[4]={1,0,-1,0}, dy[4]={0,-1,0,1};

// 检查点pos是否越界
bool check(pii pos) {
    int x=pos.first;
    int y=pos.second;
    return x>=1 && x<=n && y>=1 && y<=m;
}

void printb() {
    cout<<"B: \n";
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n";    
}

queue<pii> q;
void bfs() {
    // cout<<"dbg: "<<src.first<<" "<<src.second<<"\n";
    while(!q.empty()) {
        pii pos=q.front();
        q.pop();
        for(int i=0; i<4; i++) {
            pii newpos={pos.first+dx[i], pos.second+dy[i]};
            if(check(newpos)) {
                // 根据BFS层次访问的特点，newpos点被第一次访问时，一定就是最短距离
                if(b[newpos.first][newpos.second]==-1) {
                    b[newpos.first][newpos.second] = b[pos.first][pos.second]+1;
                    q.push(newpos);
                }
                // printb();
            }
        }
        // printb();
    }
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            char ch;
            cin>>ch;
            a[i][j]=ch-'0';
        }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            b[i][j]=-1;

    // 把a当中为1的元素都入队
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(a[i][j]) {
                b[i][j]=0;
                q.push({i, j});
            }
    bfs();
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    
    return 0;
}