十字斩

概述

https://www.nowcoder.com/questionTerminal/d5c0c89e93f344348bbc75214f864624

游戏工程师小明购买了VR设备之后爱上了体感游戏，而最近他把他的业余时间花在了一款叫十字斩的游戏里。当你戴上VR眼镜启动游戏后，先选择一首音乐，然后会发现有一个NN的方阵呈现在你的眼前，方阵的每个格子上都有一个数字。然后伴随着音乐节拍，你需要按照时机对方阵进行一次十字斩击（同时斩掉一行和一列，而且选好了行列后不能斩到选定行列之外的格子）。斩击完了之后，矩阵会收缩成一个（N-1）（N-1）的方阵。

特别的，若该次十字斩斩到的格子数字和是本次所有十字可能里最大的，则会获得一个Perfect，如果N次十字斩都是Perfect，则可以获得FullCombo的成就。但小明的心算能力不行，至今还未能获得FullCombo的成就。所幸初始数字方阵与音乐是一一对应的，所以小明可以通过预先计算十字斩的位置然后背下来，游玩的时候根据记忆去进行十字斩位置的选择即可。

小明上了一天班已经不想写代码了，所以他拜托你来写一个程序为他计算出十字斩的方案。

O(n^3) 暴力解法

#include <bits/stdc++.h>
using namespace std;

void fuck(vector<vector<int>>*& nums, int n) {
    if (n == 0) return;
    vector<int> rowSums(n), colSums(n);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            rowSums[i] += (*nums)[i][j];
            colSums[j] += (*nums)[i][j];
        }
    }

    int mi = 0, mj = 0, mv = INT_MIN;
    for (int i = n - 1; i >= 0; i --) {
        for (int j = n - 1; j >= 0; j --) {
            if (rowSums[i] + colSums[j] - (*nums)[i][j] >= mv) {
                mv = rowSums[i] + colSums[j] - (*nums)[i][j];
                mi = i, mj = j;
            }
        }
    }
    cout << mi + 1 << " " << mj + 1 << endl;
    auto newNums = new vector<vector<int>>(n-1, vector<int>(n-1));
    int ri = 0;
    for (int i = 0; i < n; i ++) {
        if (i == mi) continue;
        int rj = 0;
        for (int j = 0; j < n; j ++) {
            if (j == mj) continue;
            (*newNums)[ri][rj] = (*nums)[i][j];
            rj ++;
        }
        ri ++;
    }
    nums->clear();
    nums = newNums;
}

int main() {
    int n; cin >> n;
    auto nums = new vector<vector<int>>(n, vector<int>(n));
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            cin >> (*nums)[i][j];
        }
    }
    for (; n > 0; n --) {
        fuck(nums, n);
    }
}

Links: 十字斩

未经允许，禁止转载，本文源站链接：https://iamazing.cn/