LintCode 600. 包裹黑色像素点的最小矩形（BFS）

1. 题目

一个由二进制矩阵表示的图，0 表示白色像素点，1 表示黑色像素点。 黑色像素点是联通的，即只有一块黑色区域。 像素是水平和竖直连接的，给一个黑色像素点的坐标 (x, y) ，返回囊括所有黑色像素点的矩阵的最小面积。

代码语言：javascript复制

样例 1:
输入：["0010","0110","0100"]，x=0，y=2
输出：6
解释：
矩阵左上角坐标是(0, 1), 右下角的坐标是(2, 2)

样例 2:
输入：["1110","1100","0000","0000"], x = 0, y = 1
输出：6
解释：
矩阵左上角坐标是(0,  0), 右下角坐标是(1, 2)

2. 解题

• 广度优先搜索所有的黑点
• 记录坐标的4个方向的极限值

代码语言：javascript复制

class Solution {
public:
    int minArea(vector<vector<char>> &image, int x, int y) {
        if(image.empty() || image[0].empty())
        	return 0;
        queue<vector<int>> q;
        q.push({x,y});
        image[x][y] = 'v';//标记走过了
        int m = image.size(), n = image[0].size();
        int l = x, r = x, u = y, b = y, i, j, k, i0, j0;
        vector<vector<int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};//方向
        while(!q.empty())
        {
        	i0 = q.front()[0];
        	j0 = q.front()[1];
        	q.pop();
        	for(k = 0; k < 4;   k)
        	{
        		i = i0 dir[k][0];
        		j = j0 dir[k][1];
        		if(i>=0 && i < m && j >=0&& j < n && image[i][j] != '0' && image[i][j] != 'v')
        		{
        			q.push({i,j});
        			image[i][j]='v';
        			l = min(l,i);//记录极限位置
        			r = max(r,i);
        			u = min(u,j);
        			b = max(b,j);
        		}
        	}
        }
        return (r-l 1)*(b-u 1);//返回面积
    }
};

100% 数据通过测试 总耗时 646 ms 您的提交打败了 34.20% 的提交!

二进制

0 人点赞