2024-12-05：构造相同颜色的正方形。用go语言，给定一个3x3的矩阵，每个格子是'B'或'W'。

你需要判断是否可以通过修改最多一个格子的颜色，使得矩阵中存在一个2x2的颜色完全相同的正方形。

如果能得到这样的正方形，返回true；否则返回false。

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

输出：true。

解释：

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

大体步骤如下：

1.创建一个函数 canMakeSquare(grid [][]byte) bool，该函数接受一个 3x3 的二维字节数组作为参数。

2.在 canMakeSquare 函数中，使用两个嵌套的循环遍历所有可能的左上角位置 (i, j)。

3.对于每个左上角位置 (i, j)，调用 check(grid [][]byte, i, j int) bool 函数进行检查。

4.check 函数接受当前左上角位置 (i, j)，遍历这个2x2的小正方形格子，检查是否有超过两个相同颜色 ('B') 的格子。

5.如果发现这个小正方形中超过两个相同颜色的格子，返回 false，否则返回 true。

6.如果所有的情况都检查完毕后没有找到符合条件的正方形，最终返回 false。

时间复杂度：

• 遍历所有可能的左上角位置需要 O(1) 的时间复杂度。• 在每个左上角位置下，检查2x2小正方形格子是否满足条件的过程复杂度是 O(1)。• 因此，总的时间复杂度为 O(1)。

空间复杂度：

• 除了输入参数之外，额外只使用了常数级别的额外空间。• 因此，总的额外空间复杂度为 O(1)。Go完整代码如下：package mainimport ( "fmt")func canMakeSquare(grid [][]byte) bool { for i := 0; i <= 1; i++ { for j := 0; j <= 1; j++ { if check(grid, i, j) { return true } } } return false}func check(grid[][]byte, x, y int) bool { count := 0 for i := 0; i <= 1; i++ { for j := 0; j <= 1; j++ { if grid[x + i][y + j] == 'B' { count++ } } } return count != 2}func main() { grid := [][]byte{{'B','W','B'},{'B','W','W'},{'B','W','B'}} fmt.Println(canMakeSquare(grid))}

Rust完整代码如下：fn can_make_square(grid: &Vec<Vec<char>>) -> bool { for i in 0..=1 { for j in 0..=1 { if check(grid, i, j) { return true; } } } false}fn check(grid: &Vec<Vec<char>>, x: usize, y: usize) -> bool { let mut count = 0; for i in 0..=1 { for j in 0..=1 { if grid[x + i][y + j] == 'B' { count += 1; } } } count != 2}fn main() { let grid = vec![ vec!['B', 'W', 'B'], vec!['B', 'W', 'W'], vec!['B', 'W', 'B'] ]; println!("{}", can_make_square(&grid));}