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

【LetMeFly】3127.构造相同颜色的正方形：打表瘾犯了

力扣题目链接：https://leetcode.cn/problems/make-a-square-with-the-same-color/

给你一个二维 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' 。

解题方法一：正常枚举

枚举每一个四方块的右下角，统计这个四方块中有多少个W。只要W的个数不是2，就能直接返回true。原因如下：

• 若W = 0，则全黑
• 若W = 1，则1白，1次修改可变成全黑
• 若W = 3，则1黑，1次修改可变成全白
• 若W = 4，则全白

如果枚举完了所有的四方块，则返回false。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

写代码的时候忘记看数据范围了，写完了才发现一定是3x3。

C++

class Solution {
public:
    bool canMakeSquare(vector<vector<char>>& grid) {
        for (int i = 1; i < grid.size(); i++) {
            for (int j = 1; j < grid.size(); j++) {
                if ((grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2) {
                    return true;
                }
            }
        }
        return false;
    }
};

Go

package main

func canMakeSquare(grid [][]byte) bool {
    for i := 1; i < len(grid); i++ {
        for j := 1; j < len(grid[0]); j++ {
            cntW := 0
            for x := -1; x < 1; x++ {
                for y := -1; y < 1; y++ {
                    if grid[i + x][j + y] == 'W' {
                        cntW++
                    }
                }
            }
            if cntW != 2 {
                return true
            }
        }
    }
    return false
}

Java

class Solution {
    public boolean canMakeSquare(char[][] grid) {
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                int cntW = 0;
                for (int x = -1; x < 1; x++) {
                    for (int y = -1; y < 1; y++) {
                        if (grid[i + x][j + y] == 'W') {
                            cntW++;
                        }
                    }
                }
                if (cntW != 2) {
                    return true;
                }
            }
        }
        return false;
    }
}

Python

from typing import List

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                if (grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2:
                    return True
        return False

解题方法二：打表

做完后发现表格大小固定为3x3，然而方法一写成了mxn。怎么办？只把len(grid)和len(grid[0])改成3然后再提交一次？好像意义不大。

既然3x3的表格最多有$2^{3\times3}=512$种情况，因此来个痛快的打表吧。

由于方法一中，W（范围0-4）只有为2这一种情况时不可行，因此不可行的情况比较少。所以决定打表枚举不可行的情况。

如何将表格和整数互相转换？grid[i][j]对应整数二进制下的低i * 3 + j位即可。W代表1，B代表0，完美。

• 时间复杂度$O(1)$，一共有14种返回false的情况，可视为常数1
• 空间复杂度$O(1)$

AC代码

Python：打表求不可行的有哪些

from typing import List

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                if (grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2:
                    return True
        return False

cannot = []
sol = Solution()
for code in range(1 << 9):
    grid = [['W' if (code & (1 << (i * 3 + j))) else 'B' for j in range(3)] for i in range(3)]
    if grid == [['B', 'W', 'B'], ['W', 'B', 'W'], ['B', 'W', 'B']]:
        print(code)
    # print(grid)
    if not sol.canMakeSquare(grid):
        cannot.append(code)
print(cannot)

# [56, 113, 146, 149, 170, 173, 227, 284, 338, 341, 362, 365, 398, 455]

Python：由表差答案

from typing import List

cannot = [56, 113, 146, 149, 170, 173, 227, 284, 338, 341, 362, 365, 398, 455]

class Solution:
    def grid2code(self, grid: List[List[str]]) -> int:
        ans = 0
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 'W':
                    ans |= (1 << (i * 3 + j))
        return ans

    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        return self.grid2code(grid) not in cannot

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141756605