二进制矩阵排列搜索 - 解题思路

这段代码使用回溯算法（DFS）来寻找满足特定条件的二进制矩阵列排列方式。

算法思路

1. 输入处理：

   • 读取矩阵的行数n和列数m
   • 读取n行二进制字符串，转换为0/1矩阵
   • 初始化每行的1的计数(one)和总和(sum)

2. 回溯搜索(DFS)：

   • 从第1列开始（第0列已固定）
   • 尝试将每一未使用的列加入当前排列：
     • 检查加入该列是否满足所有行的约束条件
     • 更新行的1的计数
     • 递归搜索下一位置
     • 回溯时恢复状态

3. 约束条件检查：

   • 对于每行，如果当前列为1：
     • 检查前一个已选列在该行是否为1（确保1的连续性）
   • 对于每行，如果当前列为0：
     • 检查是否还有未分配的1

4. 结果输出：

   • 找到有效排列后输出列索引序列

关键点

• 使用回溯法系统地尝试所有可能的列排列
• 剪枝策略：在递归前检查约束条件，减少无效搜索
• 状态维护：跟踪每行已分配的1的数量
• 时间复杂度：最坏情况下O(m!)，但实际因剪枝而降低
• 空间复杂度：O(n*m)存储矩阵和辅助数组

该算法适用于需要满足特定行约束的列排列问题，特别是二进制矩阵的排列优化场景。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 400 + 7;
char s[maxn][maxn];
int a[maxn][maxn];
int ans[maxn];
int vis[maxn], one[maxn], sum[maxn];
int n, m;
int all = 0;
void dfs(int c){
    if (all)return;
    if (c == m){
        all = 1;
        return;
    }
    for (int i = 1; i < m; ++i){
        if (vis[i] == 0){
            bool ok = 1;
            for (int j = 0; j < n; ++j){
                if (a[j][i] == 1){
                    if (one[j] && a[j][ans[c-1]] == 0){
                        ok = 0;
                        break;
                    }
                }else {
                    if (one[j] && one[j] < sum[j]){
                        ok= 0;
                        break;
                    }
                }
            }
            if (!ok)continue;
            vis[i] = 1;
            for (int j = 0; j < n; ++j){
                one[j] += a[j][i];
            }
            if (!all)ans[c] = i;
            dfs(c+1);
            vis[i] = 0;
            for (int j = 0; j < n; ++j){
                one[j] -= a[j][i];
            }
        }
    }
}
int main(){
    scanf("%d %d",&n, &m);
    memset(vis,0,sizeof vis);
    vis[0] = 1;
    for (int i = 0; i < n; ++i){
        scanf("%s",s[i]);
        if (s[i][0] == '1')one[i]++;
        for (int j = 0; s[i][j]; ++j){
            if (s[i][j] == '1')a[i][j] = 1;
            else a[i][j] = 0;
            sum[i] += a[i][j];
        }
    }
    dfs(1);
    for (int i = 0; i < m; ++i) printf("%d\n",ans[i]);
    return 0;
}