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

题面解释:

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

思路:DFS暴力回溯

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

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

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

华为机考的介绍点击这里

题目内容

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

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

$2$、方块不能重叠。

$3$、方块不能超出网格的边界。

$4$、网格中部分位置不能放置方块。

输入描述

$n\ k$

$y_1~x_1$

$y_2~x_2$

表示边长为$n$的正方形网格，有$k$个位置不能放置方块，接下来$k$行坐标对，$y$表示自上向下的第几行，$x$表示自左向右的第几列(坐标从$0$开始编号，左上角为$0\ 0$)。

$n$的范围: [$1,8$]

$k$的范围:[$0,64$]

$x、y$的范围: [$0,n$)

输出描述

最多能放下多少大方块。

样例1

输入

2 0

输出

1

说明

只能放下$1$个

样例2

输入

4 3
1 0
1 3
2 1		

输出

2

说明

最多放$2$个大方块，如下图

样例3

输入

3 3
0 1
1 2
2 0

输出

0

说明

没有位置可以放置方块。