二进制矩阵行列移位求最大1元素匹配的C++实现求助

需求说明 #

• 输入为两个同尺寸二进制矩阵a、b，矩阵尺寸为m行n列
• 支持对矩阵a执行4类移位操作：行向上移位、行向下移位、列向左移位、列向右移位
• 移位统一规则：移位时空出的矩阵边缘位置补0，移出矩阵边界的元素直接丢弃。例：3阶矩阵a=[1 1 1; 1 0 1; 0 1 1]右移1位后为[0 1 1; 0 1 0; 0 0 1]，右移2位后为[0 0 1 ; 0 0 1 ; 0 0 0 ]
• 统计规则：每次移位后，统计两矩阵同位置均为1的元素数量（0元素位置无需匹配），遍历所有合法移位场景后输出最大匹配值

现有代码基础 #

已完成无移位场景的匹配计数逻辑，搭建了左、右移位的代码框架，但上、下移位逻辑未实现，原有框架存在冗余的矩阵拷贝操作，可通过索引偏移直接计算匹配数，简化逻辑提升效率。

已实现的基础计数代码 #

int i, j;
int count=0;
int max = 0;

for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++){
            if(a[i][j] == 1 && b[i][j] == 1){
                cout << "Element found at (" << i << ", "<< j << ")"<<endl;
                count++;
                max = count;
                }
        }
    } cout <<max <<endl;

已搭建的移位框架代码 #

if(new_count<max && shift<matrix_size){
  ///Shifting to the right
  for(i=0; i<m; i++){
    for(j=0; j<n; j++){
        //new_a[i][j] = new_a[i][j+shift];
        cout << new_a[i][j]<<" ";
        count++;
    }
  } cout<<endl;
  shift++;

} else{
    cout <<" The maximum matching is: "<<max<<endl;
}

  ///Shifting to the left
  for(i=0; i<m; i++){
    for(j=n-1; j>=0; j--){
        //new_a[i][j] = new_a[i][j-shift];
        cout << new_a[i][j]<<" ";
        count++;
    }
  } cout<<endl;
  shift++;

} else{
    cout <<" The maximum matching is: "<<max<<endl;
}


///Shifting up


///Shifting down

补全后完整实现 #

核心逻辑说明 #

四个方向的移位逻辑完全对称，无需每次生成移位后的新矩阵，直接通过索引偏移计算对应原矩阵位置即可，补0区域直接跳过遍历减少无效计算：

• 右移k位：前k列补0，第j列（j≥k）元素对应原矩阵j-k列
• 左移k位：后k列补0，第j列（j<n-k）元素对应原矩阵j+k列
• 下移k位：前k行补0，第i行（i≥k）元素对应原矩阵i-k行
• 上移k位：后k行补0，第i行（i<m-k）元素对应原矩阵i+k行

可运行完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 可替换为实际输入的矩阵
    int m = 3, n = 3;
    vector<vector<int>> a = {{1,1,1}, {1,0,1}, {0,1,1}};
    vector<vector<int>> b = {{1,0,1}, {0,1,0}, {1,0,1}};
    
    int max_match = 0;
    int cur_count = 0;
    // 统计无移位场景匹配数
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] && b[i][j]) cur_count++;
        }
    }
    max_match = cur_count;
    cout << "无移位匹配数：" << cur_count << endl;

    int max_shift = max(m, n);
    // 移位步长超过矩阵尺寸后矩阵全为0，无需继续统计
    for (int k = 1; k < max_shift; k++) {
        // 右移k位统计
        cur_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = k; j < n; j++) {
                if (a[i][j - k] && b[i][j]) cur_count++;
            }
        }
        max_match = max(max_match, cur_count);
        cout << "右移" << k << "位匹配数：" << cur_count << endl;

        // 左移k位统计
        cur_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n - k; j++) {
                if (a[i][j + k] && b[i][j]) cur_count++;
            }
        }
        max_match = max(max_match, cur_count);
        cout << "左移" << k << "位匹配数：" << cur_count << endl;

        // 下移k位统计
        cur_count = 0;
        for (int i = k; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i - k][j] && b[i][j]) cur_count++;
            }
        }
        max_match = max(max_match, cur_count);
        cout << "下移" << k << "位匹配数：" << cur_count << endl;

        // 上移k位统计
        cur_count = 0;
        for (int i = 0; i < m - k; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i + k][j] && b[i][j]) cur_count++;
            }
        }
        max_match = max(max_match, cur_count);
        cout << "上移" << k << "位匹配数：" << cur_count << endl;
    }

    cout << "所有移位场景下最大匹配值为：" << max_match << endl;
    return 0;
}

示例运行输出 #

无移位匹配数：3
右移1位匹配数：2
左移1位匹配数：1
下移1位匹配数：2
上移1位匹配数：3
右移2位匹配数：1
左移2位匹配数：1
下移2位匹配数：1
上移2位匹配数：1
所有移位场景下最大匹配值为：3

内容的提问来源于stack exchange，提问作者Sam