先遍历一遍找到所有能放下方块的位置，并将方块左上角的坐标放入集合中。

对集合进行dfs。具体来说，先从集合中拿出一个坐标，若选择在此处放置方块，则创建当前集合的副本并删除集合中所有受影响的位置坐标，接着对该副本集合进行迭代；若不放置方块，则维持原集合并迭代。最后返回（1 + 副本集合dfs的返回值）与原集合dfs的返回值间的最大值即可。

# python
def main():
    n, k = map(int, input().split())
    lists = [[0 for _ in range(n)] for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        lists[x][y] = -1

    area = ((0, 0), (0, 1), (1, 0), (1, 1))
    remo = ((0, 0), (0, 1), (1, 0), (1, 1), (0, -1), (1, -1), (-1, -1), (-1, 0), (-1, 1))
    d = set()
    # 找到所有能放下方块的位置的左上角坐标并存入集合中
    for i in range(n - 1):
        for j in range(n - 1):
            flag = True
            for ax, ay in area:
                x = ax + i
                y = ay + j
                if lists[x][y] == -1:
                    flag = False
                    break
            if flag:
                d.add((i, j))

    def dfs(sets) -> int:
        if len(sets) == 0:
            return 0
        # 从集合中选取一个坐标
        (sx, sy) = sets.pop()
        # 创建集合副本
        new_sets = sets.copy()
        for cx, cy in remo:
            nx = sx + cx
            ny = sy + cy
            if (nx, ny) in new_sets:
                # 删除受影响的坐标
                new_sets.remove((nx, ny))
      # 返回放与不放的最大值  
      return max(dfs(new_sets) + 1, dfs(sets))

    print(dfs(d))


if __name__ == '__main__':
    main()

最最最简单的方法：

因为数据量很小，遍历一下就行了

import java.util.Scanner;

/**
 * @author 
 * @version 1.0
 * @description:TODO
 * @data 2024/9/27
 */
public class Main {
    //AC
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n,k,x,y,ans=0;
        n=sc.nextInt();
        k=sc.nextInt();
        int [][] graph=new int[n][n];
        for(int i=0;i<k;i++){
            x=sc.nextInt();
            y=sc.nextInt();
            graph[x][y]=-1;
        }
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1;j++){
                if(graph[i][j]>-1&&graph[i][j+1]>-1&&graph[i+1][j]>-1&&graph[i+1][j+1]>-1){
                    ans++;
                    graph[i][j]=-1;
                    graph[i+1][j]=-1;
                    graph[i][j+1]=-1;
                    graph[i+1][j+1]=-1;
                }
            }
        }
        System.out.println(ans);
    }
}

n,k = map(int,input().split())
g = [[0]*105 for _ in range(105)]
dx = [-1,0,-1,0]
dy = [-1,-1,0,0]
def dfs(x,y):
    if x>=n:
        return 0
    can_place= True
    for i in range(4):
        if g[x+dx[i]][y+dy[i]]==1:
            can_place = False
    res = 0
    if can_place:
        for i in range(4):
            g[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):
            g[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())
    g[x][y]=1
res = dfs(1,1)
print(res)       
    

还是有一个没通过

n, k = map(int, input().split())
mp = []
for _ in range(k):
    mp.append(list(map(int, input().split())))

g = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if [i, j] not in mp:
            g[i][j] = 1
            
vis = [[False] * n for _ in range(n)]
res1 = 0
#先遍历列再遍历行
for j in range(n-1):
    for i in range(n-1):
        if i + 1 >= n or j + 1 >= n:
            continue
        if vis[i][j] or vis[i][j + 1] or vis[i + 1][j] or vis[i + 1][j + 1]:
            continue
        if g[i][j] == 1 and g[i][j+1] == 1 and g[i+1][j] == 1 and g[i+1][j+1] == 1:
            res1 += 1
            vis[i][j], vis[i][j + 1], vis[i + 1][j], vis[i + 1][j + 1] = True,True,True,True
#先遍历行再遍历列
vis2 = [[False] * n for _ in range(n)]
res2 = 0

for i in range(n-1):
    for j in range(n-1):
        if i + 1 >= n or j + 1 >= n:
            continue
        if vis2[i][j] or vis2[i][j + 1] or vis2[i + 1][j] or vis2[i + 1][j + 1]:
            continue
        if g[i][j] == 1 and g[i][j+1] == 1 and g[i+1][j] == 1 and g[i+1][j+1] == 1:
            res2 += 1
            vis2[i][j], vis2[i][j + 1], vis2[i + 1][j], vis2[i + 1][j + 1] = True,True,True,True


print(max(res1, res2))

修复一下下面大神没法过全部案例的情况

#include<iostream>
#include<vector>

using namespace std;


int main() {
    int n,k;
    cin>>n>>k;
    vector<vector<int>> grid(n,vector<int>(n,0));

    for (int i = 0; i < k; i++) {
        int x,y;
        cin>>x>>y;
        grid[x][y] = 1;
    }

    int res = 0;
    vector<vector<bool>> visited(n,vector<bool>(n,false));
    vector<vector<bool>> visited2(n,vector<bool>(n,false));

    // 贪心：以大方块左上角为基础，可以放置便进行标记，遍历全部的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){
            int x = i;
            int y = j;
        if (x+1 < n &&y+1 < n &&
            grid[x][y] == 0 && visited[x][y] == false &&
            grid[x+1][y] == 0 && visited[x+1][y] == false &&
            grid[x][y+1] == 0 && visited[x][y+1] == false &&
            grid[x+1][y+1] == 0 && visited[x+1][y+1] == false) {
                res++;
                visited[x][y] = true;
                visited[x+1][y] = true;
                visited[x][y+1] = true;
                visited[x+1][y+1] = true;
            }

        }
    }
    int res2 = 0;
    for (int i = 0; i < n; i++) {//列
        for (int j = 0; j < n; j++){ //行
            int y = i;
            int x = j;
        if (x+1 < n &&y+1 < n &&
            grid[x][y] == 0 && visited2[x][y] == false &&
            grid[x+1][y] == 0 && visited2[x+1][y] == false &&
            grid[x][y+1] == 0 && visited2[x][y+1] == false &&
            grid[x+1][y+1] == 0 && visited2[x+1][y+1] == false) {
                res2++;
                visited2[x][y] = true;
                visited2[x+1][y] = true;
                visited2[x][y+1] = true;
                visited2[x+1][y+1] = true;
            }

        }
    }
    cout<<max(res,res2)<<endl;
    return 0;
}

贪心：以大方块左上角为基础，可以放置便进行标记，遍历全部的位置

#include<iostream>
#include<vector>

using namespace std;

int dir[4][2] = {1,0,0,1,0,-1,-1,0};

int main() {
    int n,k;
    cin>>n>>k;
    vector<vector<int>> grid(n,vector<int>(n,0));

    for (int i = 0; i < k; i++) {
        int x,y;
        cin>>x>>y;
        grid[x][y] = 1;
    }

    int res = 0;
    vector<vector<bool>> visited(n,vector<bool>(n,false));
    // 贪心：以大方块左上角为基础，可以放置便进行标记，遍历全部的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){
            int x = i;
            int y = j;
        if (x+1 < n &&y+1 < n &&
            grid[x][y] == 0 && visited[x][y] == false &&
            grid[x+1][y] == 0 && visited[x+1][y] == false &&
            grid[x][y+1] == 0 && visited[x][y+1] == false &&
            grid[x+1][y+1] == 0 && visited[x+1][y+1] == false) {
                res++;
                visited[x][y] = true;
                visited[x+1][y] = true;
                visited[x][y+1] = true;
                visited[x+1][y+1] = true;
            }

        }
    }

    cout<<res<<endl;
    return 0;
}

题面解释:

在一个$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会员可以通过点击题目上方《已通过》查看其他通过代码来学习。