【深度优先搜索8】俄罗斯方块
题面解释:
在一个n×n的网格游戏中，可以放置由4个小方块组成的大方块（类似俄罗斯方块）。网格中有k个位置不能放置方块，这些位置通过坐标给出。我们需要计算在不重叠、不超出边界的情况下，最多可以放置多少个大方块。输入的第一行包含n和k，接下来有k行给出不能放置方块的坐标对(y,x)。输出结果为最多能放下的大方块数量。
思路:DFS暴力回溯
本题非常类似于:LeetCode 1240. 铺瓷砖。
P14342.【深度优先搜索8】俄罗斯方块
本题为2024年9月25日华为机考原题
华为机考的介绍点击这里
题目内容
在俄罗斯方块游戏中，只有下面1种大方块，由四个正方形小方块组成。现在，请计算在给定网格大小的情况下，最多可以放置多少个大方块。
具体规则如下:
1、网格为正方形网络。
2、方块不能重叠。
3、方块不能超出网格的边界。
4、网格中部分位置不能放置方块。
输入描述
n k
y1 x1
y2 x2
表示边长为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
说明
没有位置可以放置方块。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
