審題：
本題需要我們找出所有0距離最近的1的曼哈頓距離
思路：
方法一：多源bfs分析曼哈頓距離：
求法1：公式法，帶入題目公式，利用|x1-x2|+|y1-y2|求出
求法2：曼哈頓距離就是最短距離
本題有多個起源點，也就是1，我們可以把他們都加入到隊列中，然后按照正常的bfs流程走。
若用單源的bfs走就是遍歷每個0去搜索，不過會超時
解題：
（1）預處理
#include<iostream> #include<queue> #include<cstring> using namespace std; int n,m; const int N = 1010; char vv[N][N];//記錄字符 typedef pair<int,int> PII; queue<PII> q;//記錄待走坐標 int dis[N][N];//記錄到該坐標最短距離 //方向數組 int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0};1.用char二維數組記錄是因為題目中給的是不帶空格的輸入，用int會被識別為一個數字
（2）main函數邏輯
int main() {//錄入數據cin >> n >> m;memset(dis,-1,sizeof(dis));for(int i = 1; i <= n ; i++){for(int j = 1; j <= m; j++){cin >> vv[i][j];if(vv[i][j] == '1')//記錄坐標和標記距離{q.push({i,j});dis[i][j] = 0;}}}bfs();//輸出數據for(int i = 1; i <= n ; i++){for(int j = 1; j <= m; j++){cout << dis[i][j] << " ";}cout << endl;}return 0; }（3）bfs
void bfs() {while(!q.empty()){size_t size = q.size();for(int i = 0; i < size; i++){auto pos = q.front();q.pop();for(int j = 0; j < 4; j++){int newx = pos.first + dx[j];int newy = pos.second + dy[j];if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&dis[newx][newy] == -1){dis[newx][newy] = dis[pos.first][pos.second] + 1;q.push({newx,newy});}}}} }1.這里我們不能使用vector的二維方向數組，因為對空間有要求
2.核心就是對沒遍歷過的位置進行距離更新，因為bfs的性質，最先搜索到的就是最短距離。
而當前位置最短距離就是前一個位置的最短距離+1
矩陣距離
)
