廣度優(yōu)先搜索 + 多源最短路徑

原題鏈接

感悟：這個(gè)題啊，其實(shí)可以轉(zhuǎn)換個(gè)思路，轉(zhuǎn)換成1的格子到其他0的格子的最短路徑，就基本知道是多源最短路徑的問(wèn)題。說(shuō)到多源最短路徑有個(gè)大名鼎鼎的Floyd算法，不過(guò)本題不用這么麻煩，因?yàn)樽x懂題目可知邊的權(quán)值都是1(相鄰邊)?？梢灾苯佑脧V搜，等下詳細(xì)說(shuō)。還有啊，今天終于報(bào)上了心心念念的老師的算法基礎(chǔ)課，很激動(dòng)，盡管自己水平不咋地，還是得加油啊?。?！

廣搜的基本框架可以看看這篇 廣搜框架

本題思路

從1格子開(kāi)始，往其他地方搜索，走一步距離加一（挺簡(jiǎn)單的，沒(méi)啥好說(shuō)）

• 利用廣搜求多源最短路徑
• 儲(chǔ)存地圖g，狀態(tài)d，都用二維數(shù)組
• 開(kāi)始狀態(tài)：1格子的地方距離都是0；最終狀態(tài)：其他地方走到，并記錄距離；
• 二維的四個(gè)方向
• 每走一步距離+1

pair

pair<int, int> p; //第一個(gè)坐標(biāo)p.first,第二個(gè)坐表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}); //加入的時(shí)候應(yīng)該將x,y坐標(biāo)作為一個(gè)整體加入
            }
    
    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;
}