531 Lonely Pixel I

531. Lonely Pixel I

1. Question

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

A black lonely pixel is character 'B' that located at a specific position where the same row and same column don't have any other black pixels.

Example:

Input:
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]


Output: 3

Explanation: All the three 'B's are black lonely pixels.

Note:

1. The range of width and height of the input 2D array is [1,500].

2. Implementation

(1) DFS

public class Solution {
    public int findLonelyPixel(char[][] picture) {
        if (picture == null || picture.length == 0) {
            return 0;
        }

        int m = picture.length, n = picture[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int lonelyPixel = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    int count = 0;
                    for (int[] direction : directions) {
                        if (!findLonelyPixelByDFS(i, j, picture, direction)) {
                            break;
                        }
                        else {
                            ++count;
                        }
                    }

                    if (count == 4) {
                        ++lonelyPixel;
                    } 
                }
            }
        }
        return lonelyPixel;
    }

    public boolean findLonelyPixelByDFS(int row, int col, char[][] picture, int[] direction) {
        row += direction[0];
        col += direction[1];

        if (row < 0 || row >= picture.length || col < 0 || col >= picture[0].length) {
            return true;
        }


        if (picture[row][col] == 'B') {
            return false;
        }

        return findLonelyPixelByDFS(row, col, picture, direction);
    }
}

3. Time & Space Complexity

DFS: 时间复杂度O(mn * Max(m, n)), m为picture的行数， n为picture的列数，分析：最坏的情况是每个pixel都是black，然后我们通过dfs从up, down, left, down四个方向检查该pixel是否lonely，这个过程需要时间O(max(m, n)), 空间复杂度: O(max(m, n))。