算法题（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

矩阵距离