题解

问题分析

题目要求在一个 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)$。

题目内容

某数据中心机房内摆放了M排N列机柜，现需要在每排选择一个机柜安装监控器来监视本排机柜的用电量，由于监控器在安装位置太近的话会产生相互干扰，安装时需要满足条件:安装监控器的机柜不能在同一排或同一列，并且不能在同一斜线上($45$°或$135$*的正斜线)，请问一共有多少种监控器安装方案。

输入描述

机柜排数$M$和列数$N$，值的范围[$1，15$);

输出描述

监控器安装方案数量。 如果没有方案返回$0$。

样例1

输入

2 3

输出

2

说明

第二排监控器需安装在第一排监控器相距$2$列以上的机柜，共有$2$种安装方案。图中$0$代表未安装监视器的机柜，$1$代表安装监控器的机柜。

$1$.方案1

$2$.方案$2$

样例2

输入

3 3

输出

0

说明

无法同时满足监控器所在机柜不在同一排、同一列、同一斜线上。图中$0$代表未安装监视器的机柜，$1$代表安装监控器的机柜。

$1$.第一排监控器所在机柜和第三排监控器所在机柜在同一列。

$2$.第二排监控器所在机柜和第三排监控器所在机柜在同一斜线。