302. minimum rectangular BFS with all black pixels

 302. The smallest rectangle containing all black pixels

Pictures are often represented by two-dimensional matrix in computer processing .

Give you a size of m x n The binary matrix of  image Represents a black and white picture ,0  Represents white pixels ,1  Represents black pixels .

Black pixels are connected to each other , in other words , There will only be a piece of black pixels connected together in the picture . Pixels are connected horizontally or vertically .

Here are two integers x and y Indicates the position of a black pixel , Please find out the smallest rectangle containing all black pixels （ Align with axis ）, And returns the area of the rectangle .

You must design and implement a system with less time complexity than  O(mn) Algorithm to solve this problem .

Example 1：

Input ：image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output ：6
Example 2：

Input ：image = [["1"]], x = 0, y = 0
Output ：1
 

Tips ：

m == image.length
n == image[i].length
1 <= m, n <= 100
image[i][j] by '0' or '1'
1 <= x < m
1 <= y < n
image[x][y] == '1'
image The black pixels in form only one Components

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success , This question is very watery , At most mid?

Method ：BFS

 1. Extend from a given black area point

2. Take the maximum 、 The smallest x and y

3. The actual width is obtained by subtracting from the coordinate difference , Multiply to get the smallest rectangle

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);
    }

}