#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> grid;
int res = 0;
int m, n;

bool is_valid(int row, int col) {
    for (int i = 0; i < m; i++) {
        if (grid[i][col] == 1) return false;
    }
    for (int i = 0; i < n; i++) {
        if (grid[row][i] == 1) return false;
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (grid[i][j] == 1) return false;
    }
    for (int i = row, j = col; i >= 0 && j <= n - 1; i--, j++) {
        if (grid[i][j] == 1) return false;
    }
    return true;
}

void dfs(vector<vector<int>>& grid, int row) {
    if (row == m) {
        res++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (is_valid(row, i)) {
            grid[row][i] = 1;
            dfs(grid, row + 1);
            grid[row][i] = 0;
        } else {
            continue;
        }
    }
}

int main() {
    cin >> m >> n;
    grid.resize(m, vector<int>(n, 0));
    dfs(grid, 0);
    cout << res << endl;
    return 0;
}

题解

问题分析

题目要求在一个 m * n 的矩阵中，给每一排的机柜放置一个监控器（每行只能放一个），同时要满足以下限制条件：

1. 每列只能放一个监控器。
2. 不能在同一条对角线上（即 45度 和 135度 的斜线）放置两个监控器。

该问题可以看成是一个变形的 "N 皇后" 问题，目标是计算出满足所有限制条件的不同放置方案的数量。

解题思路

我们可以使用深度优先搜索（DFS）和回溯算法来求解。具体步骤如下：

1. 定义状态变量：

   • column_vis：用于记录已经被监控器占用的列。
   • left_vis：用于记录已经被占用的正对角线。对角线的索引为 ROW + COL ，也就是说ROW + COL相同的都在同一行
   • right_vis：用于记录已经被占用的反对角线。对角线的索引为ROW - COl，也就是说ROW - COL相同的都在同一行

2. 递归函数 dfs(row)：

   • 该函数尝试在当前行 row 放置一个监控器。
   • 如果 row 等于 n（行数），则说明已经成功放置了所有监控器，返回 1 表示找到一种有效方案。
   • 初始化 ans 为 0，用于累加有效方案的数量。

3. 循环遍历每一列：

   • 遍历当前行中所有列，尝试在每个列位置放置一个监控器。
   • 检查当前列和两条对角线是否已经被占用：
     • 如果 col 在 column_vis，或 left 在 left_vis，或 right 在 right_vis，则跳过当前列，继续尝试其他列。
   • 如果当前列可用，则将其加入对应的集合（表示该列和对角线被占用），并递归调用 dfs(row + 1)，继续放置下一行的监控器。
   • 回溯：撤销当前行的放置，将 col、left 和 right 从对应集合中移除，尝试其他放置方法。

4. 返回结果：

   • 初始调用 dfs(0) 开始从第 0 行放置监控器。
   • 最终返回所有可能的有效方案数。

代码实现

python

n, m = map(int, input().split())

# 初始化集合记录列和对角线的占用情况
column_vis = set()
left_vis = set()
right_vis = set()

def dfs(row):
    # 如果当前行已经是第 n 行，说明前面的行已成功放置，找到一个有效方案
    if row == n:
        return 1
    
    ans = 0  # 统计方案数
    for col in range(m):
        # 计算当前单元格的正对角线和反对角线标识
        left = row + col
        right = row - col
        
        # 检查是否可以放置监控器
        if col in column_vis or left in left_vis or right in right_vis:
            continue
        
        # 放置监控器并标记占用
        column_vis.add(col)
        left_vis.add(left)
        right_vis.add(right)
        
        # 递归搜索下一行
        ans += dfs(row + 1)
        
        # 回溯，移除占用标记
        column_vis.remove(col)
        left_vis.remove(left)
        right_vis.remove(right)
    
    return ans

# 输出所有有效方案数
print(dfs(0))

java

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    static int n, m;
    static HashSet<Integer> column_vis = new HashSet<>(); // 记录已占用的列
    static HashSet<Integer> left_vis = new HashSet<>();   // 正对角线 (row + col)
    static HashSet<Integer> right_vis = new HashSet<>();  // 反对角线 (row - col)

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.close();
        
        System.out.println(dfs(0));
    }

    static int dfs(int row) {
        if (row == n) {
            return 1; // 已放置完所有行，找到一个合法方案
        }
        
        int ans = 0;
        for (int col = 0; col < m; col++) {
            int left = row + col;
            int right = row - col;
            
            // 检查列和对角线是否被占用
            if (column_vis.contains(col) || left_vis.contains(left) || right_vis.contains(right)) {
                continue;
            }
            
            // 放置监控器并标记该列和对角线
            column_vis.add(col);
            left_vis.add(left);
            right_vis.add(right);
            
            // 递归调用下一行
            ans += dfs(row + 1);
            
            // 回溯，移除占用标记
            column_vis.remove(col);
            left_vis.remove(left);
            right_vis.remove(right);
        }
        return ans;
    }
}

C++

#include <iostream>
#include <unordered_set>
using namespace std;

int n, m;
unordered_set<int> column_vis;  // 记录已占用的列
unordered_set<int> left_vis;    // 记录正对角线占用情况 (row + col)
unordered_set<int> right_vis;   // 记录反对角线占用情况 (row - col)

int dfs(int row) {
    if (row == n) {
        return 1;  // 已放置完所有行，找到一个合法方案
    }
    
    int ans = 0;
    for (int col = 0; col < m; ++col) {
        int left = row + col;
        int right = row - col;
        
        // 检查列和对角线是否被占用
        if (column_vis.count(col) || left_vis.count(left) || right_vis.count(right)) {
            continue;
        }
        
        // 放置监控器并标记该列和对角线
        column_vis.insert(col);
        left_vis.insert(left);
        right_vis.insert(right);
        
        // 递归调用下一行
        ans += dfs(row + 1);
        
        // 回溯，移除占用标记
        column_vis.erase(col);
        left_vis.erase(left);
        right_vis.erase(right);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    cout << dfs(0) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：由于使用了回溯法，时间复杂度为 $O(N!)$，其中 N 是行数。
• 空间复杂度：需要额外的空间存储列和对角线的占用情况，空间复杂度为 $O(N)$。