网易互娱2023校园招聘在线笔试－游戏研发工程师（第一批）2.十字斩-研发

问题介绍游戏工程师小明购买了VR设备之后爱上了体感游戏而最近他把他的业余时间花在了一款叫十字斩的游戏里。当你戴上VR眼镜启动游戏后先选择一首音乐然后会发现有一个N*N的方阵呈现在你的眼前方阵的每个格子上都有一个数字。然后伴随着音乐节拍你需要按照时机对方阵进行一次十字斩击同时斩掉一行和一列而且选好了行列后不能斩到选定行列之外的格子。斩击完了之后矩阵会收缩成一个N-1*N-1的方阵。特别的若该次十字斩斩到的格子数字和是本次所有十字可能里最大的则会获得一个Perfect如果N次十字斩都是Perfect则可以获得FullCombo的成就。但小明的心算能力不行至今还未能获得FullCombo的成就。所幸初始数字方阵与音乐是一一对应的所以小明可以通过预先计算十字斩的位置然后背下来游玩的时候根据记忆去进行十字斩位置的选择即可。小明上了一天班已经不想写代码了所以他拜托你来写一个程序为他计算出十字斩的方案。时间限制C/C 1秒其他语言2秒空间限制C/C 64M其他语言128M输入描述每个输入数据包含一个测试点。第一行为一个正整数N方阵的大小。0 N 500接下来N行每行有N个数字第i行第j个数字表示方阵i行j列上的数字是多少对于每个数字保证是非负整数且范围在[0, 65535]内。输出描述输出N行每行两个整数nm第i行的nm表示第i次斩击时斩击第n行和第m列的数字和是最大的。注意如果此时有多种方案输出n最小的更小的数字更方便小明记忆如果还有多种方案输出m最小的。而且n、m的坐标是对于当前的N 1 – i大小方阵而言并不是对于一开始N*N大小的方阵而言更加详细的说明参见下方样例说明。示例1输入例子3 1 0 0 0 10 10 0 10 10输出例子2 2 1 2 1 1例子说明对于第一轮我们斩击2行2列、2行3列、3行2列、3行3列的数字和都是最大的为30行列重复的那个格子的数字并不会被计算两次但因为希望n和m都最小所以我们的斩击选择为2 2斩击之后剩余的上下左右四个矩阵收缩为新的矩阵1 00 10此时最优的斩击选择就是1 2 (注意是新方阵下的坐标而非原方阵的第1行3列)然后剩下一个1*1的方阵只有唯一的斩击选择1 1了第一种解法暴力直接一股脑的遍历每次都算出哪个位置斩击是最大的然后进行删除。不过这样的时间复杂度为ON3通不过全部测试用例。#include bits/stdc.h using namespace std; class vector2 { public: int x, y; vector2(int _x, int _y) : x(_x), y(_y) {} }; int N; int a[505][505] { 0 }; int SumOfX(int x) { int sum 0; for (int j 1; j N; j) { sum a[x][j]; } return sum; } int SumOfY(int y) { int sum 0; for (int i 1; i N; i) { sum a[i][y]; } return sum; } void DeleteXY(int x, int y) { for (int i 1; i N; i) { for (int j y 1; j N; j) { a[i][j-1] a[i][j]; } } for (int i x 1; i N; i) { for (int j 1; j N; j) { a[i-1][j] a[i][j]; } } N--; } vector2 CheckMax() { if (N 1) { return vector2(1, 1); } int max 0; vector2 ans(0, 0); for (int i 1; i N; i) { for (int j 1; j N; j) { int sum SumOfX(i) SumOfY(j)-a[i][j]; if (sum max) { max sum; ans vector2(i, j); } } } DeleteXY(ans.x, ans.y); return ans; } int main() { cin N; for (int i 1; i N; i) { for (int j 1; j N; j) { cin a[i][j]; } } while (N 1) { vector2 ans CheckMax(); cout ans.x ans.y endl; } cout 1 1 endl; return 0; }第二种解法前缀和在暴力的基础上加上两个数组分别表示各行各列的前缀和。这样就可以省去计算每个位置十字和时间复杂度只有ON²满足题目要求。#include bits/stdc.h using namespace std; class vector2 { public: int x, y; vector2(int _x, int _y) : x(_x), y(_y) {} }; int N; int a[505][505] { 0 }; int b[505][505] { 0 };//行上的前缀和 int c[505][505] { 0 };//列上的前缀和 //删除第x行第y列 void DeleteXY(int x, int y) { for (int i 1; i N; i) { for (int j y 1; j N; j) { b[i][j-1]b[i][j]-a[i][y];//b往左走 } } for (int i x 1; i N; i) { for (int j 1; j N; j) { b[i - 1][j] b[i][j];//b往上走 } } for (int j 1; j N; j) { for (int ix1; i N; i) { c[i - 1][j] c[i][j] - a[x][j];//c往上走 } } for (int i 1; i N; i) { for (int j y 1; j N; j) { c[i][j - 1] c[i][j];//c往左走 } } for (int i 1; i N; i) { for (int j y 1; j N; j) { a[i][j - 1] a[i][j];//a往左走 } } for (int i x 1; i N; i) { for (int j 1; j N; j) { a[i - 1][j] a[i][j];//a往上走 } } N--; } vector2 CheckMax()//寻找斩击哪个位置最大 { if (N 1) { return vector2(1, 1); } int max 0; vector2 ans(0, 0); for (int i 1; i N; i) { for (int j 1; j N; j) { int temp b[i][N] c[N][j] - a[i][j]; if (temp max) { max temp; ans vector2(i, j); } } } DeleteXY(ans.x, ans.y); return ans; } int main() { cin N; for (int i 1; i N; i) { for (int j 1; j N; j) { cin a[i][j]; b[i][j] b[i][j-1] a[i][j]; c[i][j] c[i-1][j] a[i][j]; } } while (N 1) { vector2 ans CheckMax(); cout ans.x ans.y endl; } cout 1 1 endl; return 0; }