AcWing 173. 矩阵距离

广度优先搜索 + 多源最短路径

原题链接

感悟：这个题啊，其实可以转换个思路，转换成1的格子到其他0的格子的最短路径，就基本知道是多源最短路径的问题。说到多源最短路径有个大名鼎鼎的Floyd算法，不过本题不用这么麻烦，因为读懂题目可知边的权值都是1(相邻边)。可以直接用广搜，等下详细说。还有啊，今天终于报上了心心念念的老师的算法基础课，很激动，尽管自己水平不咋地，还是得加油啊！！！

广搜的基本框架可以看看这篇 广搜框架

本题思路

从1格子开始，往其他地方搜索，走一步距离加一（挺简单的，没啥好说）

• 利用广搜求多源最短路径
• 储存地图g，状态d，都用二维数组
• 开始状态：1格子的地方距离都是0；最终状态：其他地方走到，并记录距离；
• 二维的四个方向
• 每走一步距离+1

pair

pair<int, int> p; //第一个坐标p.first,第二个坐表p.second;

ACcode

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1005;
typedef pair<int, int> pp;

int n, m;
char g[N][N];
int d[N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs()
{
    memset(d, -1, sizeof d);
    queue<pp> q;
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == '1')
            {   
                d[i][j] = 0;
                q.push({i, j}); //加入的时候应该将x,y坐标作为一个整体加入
            }
    
    while(q.size())
    {
        auto t = q.front(); q.pop();
        
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny] == -1)
            {
                d[nx][ny] = d[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) 
        scanf("%s", g[i]);
        
    bfs();
    
    for(int i = 0; i < n; i++)
    {   
        for(int j = 0; j < m; j++)
            printf("%d ", d[i][j]);
        printf("\n");
    }
    
    return 0;
}