LeetCode 补充题 150. 棋盘四邻域翻转
题目描述
牛客原题： ✅ 补充题 150. 棋盘四邻域翻转
给定一个
4×4的01棋盘board和一串从1开始编号的坐标operations。每次翻转指定格的上下左右四邻棋子，越界邻居忽略，不翻转中心格。按次序执行所有操作，返回最终棋盘。
示例 1：
输入：
board = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]], operations = [[1,1]]
输出：[[0,1,0,0],[1,0,0,0],[0,0,0,0],[0,0,0,0]]
解释： 坐标从 1 开始，只有 (1,2)、(2,1) 被翻转；中心 (1,1) 不变，越界邻居忽略。
提示：
- 棋盘大小固定为
4×4，元素为0或1。 - 操作坐标按
[行,列]表示，两者范围均为1…4。 - 仅翻转合法四邻格，不翻转中心格。
题意分析
操作顺序已经给定，要求的是执行后的棋盘，不是搜索最少操作次数。每次只影响固定四个邻格，因此按定义模拟即可，棋盘可以原地更新。
解法：枚举四邻坐标并异或翻转
核心思路
[!blue]
先将输入的 1 起始坐标减 1，转换为数组下标。用四个偏移分别表示上下左右，不包含
(0,0)，从而中心格不会被翻转。对每个邻格先判断行列是否都在
[0,4)，合法时执行board[r][c] ^= 1，将 0 与 1 互换。越界邻居直接忽略，不需要移动操作中心。每轮之后棋盘恰好是执行完当前前缀操作的状态；同一格被翻转两次会恢复，直接依次执行自然处理重复操作。四个方向与棋盘大小固定，所以每次操作只需常数工作量。
解题步骤
- 把每个操作坐标从 1 起始转换为 0 起始。
- 枚举上下左右偏移，只处理棋盘内的邻格。
- 邻格与 1 异或完成翻转，中心保持不变。
代码实现
class Solution {
public int[][] flip(int[][] board, int[][] operations) {
int[][] directions = {
{
1,
0
},
{
-1,
0
},
{
0,
1
},
{
0,
-1
}
};
for (int[] op : operations) {
for (int[] d : directions) {
int r = op[0] - 1 + d[0];
int c = op[1] - 1 + d[1];
if (r >= 0 && r < 4 && c >= 0 && c < 4) {
board[r][c] ^= 1;
}
}
}
return board;
}
}
func flip(board, operations [][]int) [][]int {
directions := [][2]int{
{
1,
0,
},
{
-1,
0,
},
{
0,
1,
},
{
0,
-1,
},
}
for _, op := range operations {
for _, d := range directions {
r, c := op[0]-1+d[0], op[1]-1+d[1]
if r >= 0 && r < 4 && c >= 0 && c < 4 {
board[r][c] ^= 1
}
}
}
return board
}
复杂度分析
- 时间复杂度：q次操作耗时 $O(q)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
一次异或切换 0 与 1，两次翻转抵消；坐标转换与中心是否翻转必须按题目约定处理。
易错点总结
[!yellow]
坐标从1开始；不翻转中心；本题不是求最少操作数。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！