7-402 纵横

莫大侠练成纵横剑法，走上了杀怪路，每次仅出一招。这次，他遇到了一个正方形区域，由n×n个格子构成，每个格子（行号、列号都从1开始编号）中有若干个怪。莫大侠施展幻影步，抢占了一个格子，使出绝招“横扫四方”，就把他上、下、左、右四个直线方向区域内的怪都灭了（包括抢占点的怪）。请帮他算算他抢占哪个位置使出绝招“横扫四方”能杀掉最多的怪。如果有多个位置都能杀最多的怪，优先选择按行优先最靠前的位置。例如样例中位置（1，2）、（1，3），（3，2），（3，3）都能杀5个怪，则优先选择位置（1，2）。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。对于每组测试，第一行输入n（3≤n≤20），第二行开始的n行输入n×n个格子中的怪数（非负整数）。

输出格式:

对于每组测试数据输出一行，包含三个整数，分别表示莫大侠抢占点的行号和列号及所杀的最大怪数，数据之间留一个空格。

输入样例:

3
3
1 1 1
0 1 1
1 1 1
3
3 2 1
4 6 5
8 7 9
3
24 5 89
13 59 15
85 3 27

输出样例:

1 2 5
3 2 32
3 3 219

来源：

[1] 黄龙军, 等. 大学生程序设计竞赛入门—C/C++程序设计（微课视频版）, 北京:清华大学出版社, 2020.11. ISBN:9787302564744
[2] 黄龙军.程序设计竞赛入门（Python版）,北京:清华大学出版社,2021.4. ISBN:9787302571230

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>

#define MAX_N 20

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        int n;
        scanf("%d", &n);
        
        int grid[MAX_N][MAX_N];
        
        // 读入怪物数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &grid[i][j]);
            }
        }
        
        int maxMonsters = -1;
        int bestRow = 0, bestCol = 0;
        
        // 遍历所有可能的位置
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int monsterCount = 0;
                
                // 计算当前点 (r, c) 能杀掉的怪物数
                // 向上
                for (int i = r; i >= 0; i--) {
                    monsterCount += grid[i][c];
                }
                
                // 向下
                for (int i = r; i < n; i++) {
                    monsterCount += grid[i][c];
                }
                
                // 向左
                for (int j = c; j >= 0; j--) {
                    monsterCount += grid[r][j];
                }
                
                // 向右
                for (int j = c; j < n; j++) {
                    monsterCount += grid[r][j];
                }
                
                // 去掉重复计算的中心点 (r, c)
                monsterCount -= 3 * grid[r][c];
                
                // 更新最大怪物数及其位置
                if (monsterCount > maxMonsters) {
                    maxMonsters = monsterCount;
                    bestRow = r + 1; // 转换为1-based索引
                    bestCol = c + 1; // 转换为1-based索引
                }
            }
        }
        
        printf("%d %d %d\n", bestRow, bestCol, maxMonsters);
    }
    
    return 0;
}