3127. 构造相同颜色的正方形

题目描述

给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。

你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。

示例 1：

输入：grid = [["B","W","B"],["B","W","W"],["B","W","B"]]

输出：true

解释：

修改 grid[0][2] 的颜色，可以满足要求。

示例 2：

输入：grid = [["B","W","B"],["W","B","W"],["B","W","B"]]

输出：false

解释：

只改变一个格子颜色无法满足要求。

示例 3：

输入：grid = [["B","W","B"],["B","W","W"],["B","W","W"]]

输出：true

解释：

grid 已经包含一个 2 x 2 颜色相同的正方形了。

提示：

grid.length == 3
grid[i].length == 3
grid[i][j] 要么是 'W' ，要么是 'B' 。

解法

方法一：枚举

我们可以枚举每个 \(2 \times 2\) 的正方形，统计黑色和白色的个数，如果两者个数不相等，那么就可以构造一个相同颜色的正方形，返回 true。

否则，遍历结束后返回 false。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for i in range(0, 2):
            for j in range(0, 2):
                cnt1 = cnt2 = 0
                for a, b in pairwise((0, 0, 1, 1, 0)):
                    x, y = i + a, j + b
                    cnt1 += grid[x][y] == "W"
                    cnt2 += grid[x][y] == "B"
                if cnt1 != cnt2:
                    return True
        return False

class Solution {
    public boolean canMakeSquare(char[][] grid) {
        final int[] dirs = {0, 0, 1, 1, 0};
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                int cnt1 = 0, cnt2 = 0;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    cnt1 += grid[x][y] == 'W' ? 1 : 0;
                    cnt2 += grid[x][y] == 'B' ? 1 : 0;
                }
                if (cnt1 != cnt2) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Solution {
public:
    bool canMakeSquare(vector<vector<char>>& grid) {
        int dirs[5] = {0, 0, 1, 1, 0};
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                int cnt1 = 0, cnt2 = 0;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    cnt1 += grid[x][y] == 'W';
                    cnt2 += grid[x][y] == 'B';
                }
                if (cnt1 != cnt2) {
                    return true;
                }
            }
        }
        return false;
    }
};

func canMakeSquare(grid [][]byte) bool {
    dirs := [5]int{0, 0, 1, 1, 0}
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            cnt1, cnt2 := 0, 0
            for k := 0; k < 4; k++ {
                x, y := i+dirs[k], j+dirs[k+1]
                if grid[x][y] == 'W' {
                    cnt1++
                } else {
                    cnt2++
                }
            }
            if cnt1 != cnt2 {
                return true
            }
        }
    }
    return false
}

function canMakeSquare(grid: string[][]): boolean {
    const dirs: number[] = [0, 0, 1, 1, 0];
    for (let i = 0; i < 2; ++i) {
        for (let j = 0; j < 2; ++j) {
            let [cnt1, cnt2] = [0, 0];
            for (let k = 0; k < 4; ++k) {
                const [x, y] = [i + dirs[k], j + dirs[k + 1]];
                if (grid[x][y] === 'W') {
                    ++cnt1;
                } else {
                    ++cnt2;
                }
            }
            if (cnt1 !== cnt2) {
                return true;
            }
        }
    }
    return false;
}

3127. 构造相同颜色的正方形

题目描述

解法

方法一：枚举

评论