算法题（114）：矩阵距离

审题：

本题需要我们找出所有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

矩阵距离