77 。01 矩阵（542）

作者: Turbo时间限制: 1S章节: 宽度优先搜索

晚于: 2020-08-26 12:00:00后提交分数乘系数50%

截止日期: 2020-09-02 12:00:00

问题描述 :

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

0 0 0

0 1 0

0 0 0

输出:

0 0 0

0 1 0

0 0 0

示例 2:

输入:

0 0 0

0 1 0

1 1 1

输出:

0 0 0

0 1 0

1 2 1

注意:

给定矩阵的元素个数不超过 10000。

给定矩阵中至少有一个元素是 0。

矩阵中的元素只在四个方向上相邻: 上、下、左、右。

可使用以下main函数：

int main()

{

    vector<vector<int> > matrix;

    int m,n;

    cin>>m;

    cin>>n;

    char ch;

    for(int i=0; i<m; i++)

    {

        vector<int> aLine;

        for(int j=0; j<n; j++)

        {

            cin>>ch;

            aLine.push_back(ch-'0');

        }

        matrix.push_back(aLine);

    }

    vector<vector<int>> res=Solution().updateMatrix(matrix);

    for(int i=0; i<res.size(); i++)

    {

        vector<int> aLine = res[i];

        for(int j=0; j<aLine.size(); j++)

            cout<<aLine[j];

        cout<<endl;

    }

    return 0;

}

输入说明 :

首先输入矩阵的行数m和列数n，m*n<=10000

然后输入m行，每行n个字符0或1。中间无空格分隔。

输出说明 :

输出结果，0、1之间无空格。

输入范例 :

3 3 000 010 111

输出范例 :

000 010 121

#include <iostream>
#include <vector> 
#include <queue>
using namespace std;

class Solution {
public:
    const int dx[4]={0,0,-1,1};
    const int dy[4]={1,-1,0,0};
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) 
    {
        int m=matrix.size();
        int n=matrix[0].size();
        queue<pair<int,int>> q;
        vector<vector<int>> res(m,vector<int>(n,INT_MAX)) ;//相当于m*n的数组，并初始化数值为无穷大 
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
                if(matrix[i][j]==0)
                {
                    res[i][j]=0;//所有为0的点自身结果为0 
                    q.push({i,j});
                }
        }
        while(!q.empty())
        {
            pair<int,int> front=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int newx=front.first+dx[i];
                int newy=front.second+dy[i];
                if(newx>=0&&newx<m&&newy>=0&&newy<n)
                {
                    if(res[newx][newy]>res[front.first][front.second]+1)//值大于上一个值得大小加1，则更新 
                    {
                        res[newx][newy]= res[front.first][front.second]+1;
                        q.push({newx,newy}) ;//加入队列，为了搜寻其他的值 
                    } 
                }
            }
        }
        return res;
    }
};

int main()
{
    vector<vector<int> > matrix;
    int m,n;
    cin>>m;
    cin>>n;

    char ch;
    for(int i=0; i<m; i++)
    {
        vector<int> aLine;
        for(int j=0; j<n; j++)
        {
            cin>>ch;
            aLine.push_back(ch-'0');
        }
        matrix.push_back(aLine);
    }

    vector<vector<int>> res=Solution().updateMatrix(matrix);
    for(int i=0; i<res.size(); i++)
    {
        vector<int> aLine = res[i];
        for(int j=0; j<aLine.size(); j++)
            cout<<aLine[j];
        cout<<endl;
    }
    return 0;
}

 https://leetcode-cn.com/problems/01-matrix/solution/c-bfsxiang-jie-by-yi-zhi-ri-shi-jiu/