本题为2024年9月25日华为机考原题

华为机考的介绍点击这里

题目内容

在俄罗斯方块游戏中，只有下面$1$种大方块，由四个正方形小方块组成。现在，请计算在给定网格大小的情况下，最多可以放置多少个大方块。 具体规则如下:

$1$、网格为正方形网络。

【深度优先搜索8】俄罗斯方块

题面解释:

在一个$n \times n$的网格游戏中，可以放置由4个小方块组成的大方块（类似俄罗斯方块）。网格中有$k$个位置不能放置方块，这些位置通过坐标给出。我们需要计算在不重叠、不超出边界的情况下，最多可以放置多少个大方块。输入的第一行包含$n$和$k$，接下来有$k$行给出不能放置方块的坐标对$(y, x)$。输出结果为最多能放下的大方块数量。

思路:DFS暴力回溯

本题非常类似于:LeetCode 1240. 铺瓷砖。

采用深度优先搜索（DFS）和回溯法来解决大方块的摆放问题。我们通过递归遍历每个位置，判断是否可以放置一个 2x2 的大方块。