前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 542. 01 矩阵(BFS && DP)

LeetCode 542. 01 矩阵(BFS && DP)

作者头像
Michael阿明
发布2020-07-13 15:20:43
6100
发布2020-07-13 15:20:43
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

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

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

代码语言:javascript
复制
示例 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。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/01-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 BFS

直白想法,每个点开启bfs找到0就停止搜索,返回距离,更新矩阵,但是超时

代码语言:javascript
复制
class Solution {
	int r,c;
	vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
	queue<pair<int,int>> q;
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int i, j, dis;
        r = matrix.size(), c = matrix[0].size();
        for(i = 0; i < r; ++i)
        {
        	for(j = 0; j < c; ++j)
        	{
        		if(matrix[i][j] != 0)
        		{
        			vector<vector<bool>> visited(r,vector<bool> (c,false));
        			matrix[i][j] = bfs(i,j,matrix,visited);
        		}
        	}
        }
        return matrix;
    }
    int bfs(int i, int j, vector<vector<int>> &matrix, vector<vector<bool>> &visited)
    {
    	while(!q.empty())
			q.pop();
		visited[i][j] = true;
		q.push({i,j});
		int xf,yf,x,y,n,k,distance = 0;
		while(!q.empty())
		{
			n = q.size();
			while(n--)
			{
				xf = q.front().first;
				yf = q.front().second;
				q.pop();
				for(k = 0; k < 4; ++k)
				{
					x = xf+dir[k][0];
	        		y = yf+dir[k][1];
	        		if((x>=0 && x<r)&&(y>=0 && y<c) && !visited[x][y])
		        	{
		        		if(matrix[x][y] != 0)
		        		{
		        			q.push({x,y});
		        			visited[x][y] = true;
		        		}
		        		else
		        			return distance+1;
		        	}
				}
			}
			++distance;
		}
        return distance;
    }
};

换个思路:

  • 所有的为0的点先全部加入队列
  • 对队列中所有的0点开启BFS
  • 访问到了1,标记已访问,更新矩阵值为距离
代码语言:javascript
复制
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int i, j, dis = 0, r, c, n, xf, yf, x, y, k;
        r = matrix.size(), c = matrix[0].size();
        vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
        vector<vector<bool>> visited(r,vector<bool>(c,false));
        queue<pair<int,int>> q;
        for(i = 0; i < r; ++i)
        {
        	for(j = 0; j < c; ++j)
        	{
        		if(matrix[i][j] == 0)
        			q.push({i, j});
        	}
        }
        while(!q.empty())
		{
			n = q.size();
			++dis;
			while(n--)
			{
				xf = q.front().first;
				yf = q.front().second;
				q.pop();
				for(k = 0; k < 4; ++k)
				{
					x = xf+dir[k][0];
	        		y = yf+dir[k][1];
	        		if(x>=0 && x<r && y>=0 && y<c 
	        			&& !visited[x][y] && matrix[x][y] != 0)
		        	{
	        			q.push({x,y});
	        			visited[x][y] = true;
	        			matrix[x][y] = dis;
		        	}
				}
			}
		}
        return matrix;
    }
};
在这里插入图片描述
在这里插入图片描述

2.2 DP动态规划

dist[i][j]

表示该位置到0的最短距离

  • 一个点1到0的最短距离可以从他的4个邻居中+1得到(取最小的)
  • 所有0点的最短距离
dist

直接置为0

遍历2次

  • 先从左–》右,从上–》下
dist[i][j] = min(dist[i][j], dist[i-1][j]+1)

,上面的邻居+1

dist[i][j] = min(dist[i][j], dist[i][j-1]+1)

,左边的邻居+1

  • 再从从左《–右,从上《–下
dist[i][j] = min(dist[i][j], dist[i+1][j]+1)

,下面的邻居+1

dist[i][j] = min(dist[i][j], dist[i][j+1]+1)

,右边的邻居+1

代码语言:javascript
复制
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) 
    {
        int r = matrix.size(), c = matrix[0].size(), i, j;
        if (r == 0)
            return matrix;
        vector<vector<int>> dist(r, vector<int>(c, INT_MAX-100000));//防止溢出
        //边界上的1元素距离外面无穷大
        //考虑左边和上边方向
        for (i = 0; i < r; i++) 
        {
            for (j = 0; j < c; j++) 
            {
                if (matrix[i][j] == 0)
                    dist[i][j] = 0;
                else 
                {
                    if (i > 0)
                        dist[i][j] = min(dist[i][j], dist[i-1][j]+1);
                    if (j > 0)
                        dist[i][j] = min(dist[i][j], dist[i][j-1]+1);
                }
            }
        }

        //考虑右边和下边方向
        for (i = r-1; i >= 0; i--) 
        {
            for (j = c-1; j >= 0; j--) 
            {
                if (i < r-1)
                    dist[i][j] = min(dist[i][j], dist[i+1][j]+1);
                if (j < c-1)
                    dist[i][j] = min(dist[i][j], dist[i][j+1]+1);
            }
        }
        return dist;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/09/28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
    • 2.1 BFS
      • 2.2 DP动态规划
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档