题面解释:

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

思路:DFS暴力回溯

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

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

分两种情况:1.如果可以放置，就标记位置并继续探索下一个位置；如果不行，直接跳过。每次成功放置时更新最大值，最后回溯到上一步，取消放置状态。

题解

在本题中，我们需要在一个 $n \times n$ 的网格中放置尽可能多的 $2 \times 2$ 大方块，网格中有一些位置被标记为障碍物，不能放置大方块。为了解决这个问题，我们使用了深度优先搜索（DFS）和回溯法的策略。

具体步骤如下：

1. 递归遍历网格：从左上角开始，逐行逐列地检查每个位置是否可以放置一个 $2 \times 2$ 的大方块。
2. 判断放置条件：在检查当前格子时，我们需要确保这个 $2 \times 2$ 的区域内没有障碍物且没有超出网格边界。
3. 回溯：如果能够放置大方块，就将这4个位置标记为已占用，继续递归搜索下一个位置；如果不行，则跳过当前格子，继续尝试下一个位置。搜索完成后，恢复当前格子的状态，准备回溯到上一个状态。
4. 更新结果：每次成功放置一个大方块时，更新最大放置数量。

通过这种方法，我们可以有效地探索所有可能的放置方案，最终得到最多可以放置的大方块数量。

代码

java

import java.util.Scanner;

public class Main {
    static int n, k;
    static int[][] vis = new int[105][105];
    static int[] dx = {-1, -1, 0, 0}; // 移动方向数组
    static int[] dy = {-1, 0, -1, 0}; // 移动方向数组

    // 深度优先搜索
    static int dfs(int x, int y) {
        if (x >= n) return 0; // 递归边界

        boolean canPlace = true;
        for (int i = 0; i < 4; i++) {
            if (vis[x + dx[i]][y + dy[i]] == 1) canPlace = false;
        }

        int res = 0;
        if (canPlace) {
            // 标记格子为已访问
            for (int i = 0; i < 4; i++) {
                vis[x + dx[i]][y + dy[i]] = 1;
            }

            if (y < n - 1)
                res = Math.max(res, dfs(x, y + 1) + 1);
            else
                res = Math.max(res, dfs(x + 1, 1) + 1);

            // 回溯，重置访问状态
            for (int i = 0; i < 4; i++) {
                vis[x + dx[i]][y + dy[i]] = 0;
            }
        }

        // 继续尝试下一个位置
        if (y < n - 1)
            res = Math.max(res, dfs(x, y + 1));
        else
            res = Math.max(res, dfs(x + 1, 1));

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        
        for (int i = 1; i <= k; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            vis[x][y] = 1; // 读取障碍物的位置
        }

        System.out.println(dfs(1, 1)); // 从 (1, 1) 开始搜索
        sc.close();
    }
}

python

n, k = map(int, input().split())
vis = [[0] * 105 for _ in range(105)]
dx = [-1, -1, 0, 0]  # 移动方向数组
dy = [-1, 0, -1, 0]  # 移动方向数组
# 深度优先搜索
def dfs(x, y):
    if x >= n:
        return 0  # 递归边界
    can_place = True
    for i in range(4):
        if vis[x + dx[i]][y + dy[i]] == 1:
            can_place = False
    res = 0
    if can_place:
        # 标记格子为已访问
        for i in range(4):
            vis[x + dx[i]][y + dy[i]] = 1
        if y < n - 1:
            res = max(res, dfs(x, y + 1) + 1)
        else:
            res = max(res, dfs(x + 1, 1) + 1)
        # 回溯，重置访问状态
        for i in range(4):
            vis[x + dx[i]][y + dy[i]] = 0
    # 继续尝试下一个位置
    if y < n - 1:
        res = max(res, dfs(x, y + 1))
    else:
        res = max(res, dfs(x + 1, 1))
    return res
# 读取障碍物的位置
for _ in range(k):
    x, y = map(int, input().split())
    vis[x][y] = 1
# 从 (1, 1) 开始搜索
print(dfs(1, 1))

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型，避免数据溢出

int n, k; // 网格的边长和障碍物的数量
int vis[105][105]; // 访问状态数组，记录哪些格子已被占用
int dx[4] = {-1, -1, 0, 0}; // 2x2方块的行偏移量
int dy[4] = {-1, 0, -1, 0}; // 2x2方块的列偏移量

// 深度优先搜索函数
int dfs(int x, int y) {
    if (x >= n) return 0; // 递归边界：如果行数超出网格，返回0

    // 检查当前位置是否可以放置大方块
    int canPlace = 1; // 标记当前方块是否可以放置
    for (int i = 0; i < 4; i++) {
        if (vis[x + dx[i]][y + dy[i]] == 1) canPlace = 0; // 检查四个小方块位置是否已被占用
    }

    int res = 0; // 记录当前状态下可以放置的大方块数量
    if (canPlace == 1) {
        // 如果可以放置，标记这4个格子为已占用
        for (int i = 0; i < 4; i++) {
            vis[x + dx[i]][y + dy[i]] = 1;
        }

        // 递归继续探索下一个位置
        if (y < n - 1)
            res = max(res, dfs(x, y + 1) + 1); // 尝试向右移动
        else
            res = max(res, dfs(x + 1, 0) + 1); // 尝试向下移动

        // 回溯，重置访问状态
        for (int i = 0; i < 4; i++) {
            vis[x + dx[i]][y + dy[i]] = 0;
        }
    }

    // 继续尝试下一个位置（不放置当前方块）
    if (y < n - 1)
        res = max(res, dfs(x, y + 1)); // 尝试向右移动
    else
        res = max(res, dfs(x + 1, 0)); // 尝试向下移动

    return res; // 返回最大可以放置的大方块数量
}

signed main() {
    cin >> n >> k; // 输入网格的边长和障碍物数量
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y; // 读取每个障碍物的位置
        vis[x][y] = 1; // 标记障碍物的位置为已占用
    }
    cout << dfs(0, 0); // 从 (0, 0) 开始进行搜索
    return 0; // 程序结束
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

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

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

$2$、方块不能重叠。

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

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

输入描述

$n\ k$

$y_1\ x_1$

$y_2\ x_2$

...

$y_k\ x_k$

表示边长为$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

说明

没有位置可以放置方块。