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

题面解释:

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

思路:DFS暴力回溯

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

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

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

回溯法的介绍

回溯法（Backtracking）是一种通过试探所有可能的解来寻找问题的解法。它在解决组合问题、排列问题、图的遍历等问题时具有广泛应用。回溯法的核心思想是：在搜索过程中，如果当前的选择不符合条件或不能导致最终解，就撤销当前选择，返回到上一步再进行新的选择。回溯法常常结合递归进行实现。

回溯法的具体步骤：

1. 选择：在当前阶段选择一个可能的操作（比如放置方块）。
2. 递归：执行选择后，递归进入下一个状态，继续进行选择。
3. 撤销选择：如果当前选择导致无法继续前进或者得不到有效解，则撤销选择，回到上一步。
4. 结束条件：当搜索完成，或达到了最优解时，结束递归。

回溯法的关键在于“撤销选择”这一过程，它能够让我们回到上一状态，继续探索其他可能的解。通过这种方式，回溯法可以穷举所有可能方案。

回溯法在本题中的具体实现

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

具体步骤如下：

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

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

代码实现

Python 代码

n, k = map(int, input().split())
vis = [[False] * n for _ in range(n)]

for _ in range(k):
    x, y = map(int, input().split())
    vis[x][y] = True

# 深度优先搜索
def dfs(x, y):
    if x >= n-1:  # 递归边界：到达最后一行
        return 0

    # 计算下一个搜索位置
    next_x, next_y = (x + 1, 0) if y == n - 2 else (x, y + 1)

    res = 0

    # 判断是否能放置2x2方块
    if x + 1 < n and y + 1 < n and not vis[x][y] and not vis[x + 1][y] and not vis[x][y + 1] and not vis[x + 1][y + 1]:
        # 标记格子为已访问
        vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = True

        res = max(res, dfs(next_x, next_y) + 1)  # 递归继续搜索

        # 回溯，重置访问状态
        vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = False

    # 不放置方块，继续搜索
    res = max(res, dfs(next_x, next_y))

    return res

print(dfs(0, 0))  # 从 (0, 0) 开始搜索

Java 代码

import java.util.Scanner;

public class Main {
    static int n, k;
    static boolean[][] vis;

    // 深度优先搜索
    static int dfs(int x, int y) {
        if (x == n) return 0;  // 递归边界：到达最后一行

        // 计算下一个搜索位置
        int nextX = (y == n - 1) ? x + 1 : x;
        int nextY = (y == n - 1) ? 0 : y + 1;

        int res = 0;

        // 判断是否能放置2x2方块
        if (x + 1 < n && y + 1 < n && !vis[x][y] && !vis[x + 1][y] && !vis[x][y + 1] && !vis[x + 1][y + 1]) {
            // 标记格子为已访问
            vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = true;

            res = Math.max(res, dfs(nextX, nextY) + 1);  // 递归继续搜索

            // 回溯，取消标记
            vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = false;
        }

        // 不放置方块，继续搜索
        res = Math.max(res, dfs(nextX, nextY));

        return res;
    }
  
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        vis = new boolean[n][n];

        for (int i = 0; i < k; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            vis[x][y] = true;  // 读取障碍物的位置
        }

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

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, k;
bool vis[105][105];  // 访问状态数组

// 深度优先搜索函数
int dfs(int x, int y) {
    if (x == n) return 0;  // 递归边界：到达最后一行

    // 计算下一个搜索位置
    int nextX = (y == n - 1) ? x + 1 : x;
    int nextY = (y == n - 1) ? 0 : y + 1;

    int res = 0;

    // 判断是否能放置2x2方块
    if (x + 1 < n && y + 1 < n && !vis[x][y] && !vis[x + 1][y] && !vis[x][y + 1] && !vis[x + 1][y + 1]) {
        // 标记格子为已访问
        vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = true;

        res = max(res, dfs(nextX, nextY) + 1);  // 递归继续搜索

        // 回溯，重置访问状态
        vis[x][y] = vis[x + 1][y] = vis[x][y + 1] = vis[x + 1][y + 1] = false;
    }

    // 不放置方块，继续搜索
    res = max(res, dfs(nextX, nextY));

    return res;
}

int main() {
    cin >> n >> k;
  
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        vis[x][y] = true;  // 读取障碍物的位置
    }

    cout << dfs(0, 0) << endl;  // 从 (0, 0) 开始搜索
    return 0;
}

本题为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

说明

没有位置可以放置方块。