302. 包含全部黑色像素的最小矩形 BFS

60 阅读 0 评论 40 点赞

我是靠谱客的博主独特枕头，最近开发中收集的这篇文章主要介绍302. 包含全部黑色像素的最小矩形 BFS，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

302. 包含全部黑色像素的最小矩形

图片在计算机处理中往往是使用二维矩阵来表示的。

给你一个大小为 m x n 的二进制矩阵 image 表示一张黑白图片，0 代表白色像素，1 代表黑色像素。

黑色像素相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的。

给你两个整数 x 和 y 表示某一个黑色像素的位置，请你找出包含全部黑色像素的最小矩形（与坐标轴对齐），并返回该矩形的面积。

你必须设计并实现一个时间复杂度低于 O(mn) 的算法来解决此问题。

示例 1：

输入：image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
输出：6
示例 2：

输入：image = [["1"]], x = 0, y = 0
输出：1

提示：

m == image.length
n == image[i].length
1 <= m, n <= 100
image[i][j] 为 '0' 或 '1'
1 <= x < m
1 <= y < n
image[x][y] == '1'
image 中的黑色像素仅形成一个组件

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，这题很水，最多算 mid?

方法：BFS

1. 从给定黑色区域点进行扩展

2. 取到最大、最小的x和y

3. 根据坐标差相减获得实际宽度，相乘得到最小矩形

class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length;
        int n = image[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        int[] directions = new int[]{0,1,0,-1,0};
        int minX = x;
        int maxX = x;
        int minY = y;
        int maxY = y; 
        image[x][y] = 0;
        while(!queue.isEmpty()){
            int[] item = queue.poll();
            for(int i = 0; i < 4; i++){
                int x1 = item[0]+directions[i];
                int y1 = item[1]+directions[i+1];
                if(x1>=0&&x1<m&&y1>=0&&y1<n&&image[x1][y1]=='1'){
                    minX = Math.min(minX,x1);
                    maxX = Math.max(maxX,x1);
                    minY = Math.min(minY,y1);
                    maxY = Math.max(maxY,y1);
                    image[x1][y1] = 0;
                    queue.offer(new int[]{x1,y1});
                }
            }
        }

        return (maxX-minX+1)*(maxY-minY+1);
    }

}