题目描述在一个N×NN \times NN×N的网格城市中每个格子居住着若干人0∼100000 \sim 100000∼10000。存在四种类型的“自我中心者”HHH型该格子所在行中左侧所有格子的人数总和等于右侧所有格子的人数总和。VVV型该格子所在列中上方所有格子的人数总和等于下方所有格子的人数总和。DDD型该格子所在主对角线左上‑右下上左上方向所有格子的人数总和等于右下方向所有格子的人数总和。AAA型该格子所在反对角线右上‑左下上右上方向所有格子的人数总和等于左下方向所有格子的人数总和。对于边界格子超出城市范围的方向视为人数为000。一个格子可能同时满足多种类型。现需按顺序列出所有满足HHH、VVV、DDD、AAA条件的格子坐标按行优先输出。输入格式第一行为测试用例数TTT。每个测试用例第一行为整数NNNN≤100N \le 100N≤100接下来NNN行每行NNN个整数0∼100000 \sim 100000∼10000用空格分隔。输出格式对于每个测试用例按顺序输出四组结果分别对应HHH、VVV、DDD、AAA类型。每组结果第一行只包含该类型的字母如H随后若干行每行两个整数表示满足条件的格子坐标行和列从000开始编号。格子按行优先输出行从小到大同行列从小到大。若某类型没有满足条件的格子则只输出字母行。不同测试用例的输出连续之间无空行。样例输入3 3 1 2 3 4 5 6 7 8 9 3 1 1 1 1 1 1 1 4 5 7 7 6 2 4 0 8 6 1 0 7 6 8 7 5输出H V D 0 2 2 0 A 0 0 2 2 H 0 1 1 1 2 1 V 1 0 1 1 1 2 D 0 2 1 1 2 0 A 0 0 1 1 2 2 H 2 2 V 1 2 2 2 D 0 3 1 1 1 2 3 0 A 0 0 2 1 2 2 3 3题目分析本题数据范围较小N≤100N \le 100N≤100总格子数最多10410^4104。对于每个格子判断四种类型的条件本质上是对四个方向分别求和并比较相等。最直接的思路就是暴力枚举每个格子分别计算其左、右、上、下、左上、右下、右上、左下等方向的人数和然后比较。由于每个格子需要计算四个方向的累加和每个方向最多累加NNN个元素因此单个格子的计算复杂度为O(N)O(N)O(N)总复杂度O(N3)O(N^3)O(N3)。当N100N 100N100时约10610^6106次操作完全可以接受。因此无需复杂的数据结构直接模拟即可。需要注意边界处理当格子位于边界时超出城市方向视为人数为000这可以在循环累加时通过越界判断自然实现。解题思路读入数据存储矩阵a[N][N]。遍历每个格子(r, c)0≤r,cN0 \le r, c N0≤r,cNHHH型计算该行第ccc列左侧所有格子的和leftSum以及右侧所有格子的和rightSum若相等则记录坐标。VVV型计算该列第rrr行上方所有格子的和upSum以及下方所有格子的和downSum若相等则记录。DDD型沿主对角线方向向左上累加r-1, c-1直至越界得到dLeftUp向右下累加r1, c1直至越界得到dRightDown比较。AAA型沿反对角线方向向右上累加r-1, c1直至越界得到aRightUp向左下累加r1, c-1直至越界得到aLeftDown比较。将满足条件的坐标分别存入四个列表hList、vList、dList、aList。由于遍历顺序就是行优先因此列表自然按行优先排序。输出按顺序输出HHH、VVV、DDD、AAA每组先输出字母行然后逐行输出坐标若某列表为空则仅输出字母行。复杂度分析时间复杂度每个格子需进行四次累加每次累加最多遍历NNN个元素故总操作次数约为4×N2×NO(N3)4 \times N^2 \times N O(N^3)4×N2×NO(N3)。N100N100N100时约为4×1064 \times 10^64×106次可在111秒内完成。空间复杂度存储矩阵O(N2)O(N^2)O(N2)以及四个坐标列表最多存储O(N2)O(N^2)O(N2)个坐标总体O(N2)O(N^2)O(N2)。代码实现// City of Egocentrics// UVa ID: 11620// Verdict: Accepted// Submission Date: 2026-06-23// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intN;cinN;vectorvectorinta(N,vectorint(N));for(inti0;iN;i)for(intj0;jN;j)cina[i][j];vectorpairint,inthList,vList,dList,aList;for(intr0;rN;r){for(intc0;cN;c){// 计算 HintleftSum0,rightSum0;for(inti0;ic;i)leftSuma[r][i];for(intic1;iN;i)rightSuma[r][i];if(leftSumrightSum)hList.push_back({r,c});// 计算 VintupSum0,downSum0;for(inti0;ir;i)upSuma[i][c];for(intir1;iN;i)downSuma[i][c];if(upSumdownSum)vList.push_back({r,c});// 计算 D主对角线intdLeftUp0,dRightDown0;for(intir-1,jc-1;i0j0;--i,--j)dLeftUpa[i][j];for(intir1,jc1;iNjN;i,j)dRightDowna[i][j];if(dLeftUpdRightDown)dList.push_back({r,c});// 计算 A反对角线intaRightUp0,aLeftDown0;for(intir-1,jc1;i0jN;--i,j)aRightUpa[i][j];for(intir1,jc-1;iNj0;i,--j)aLeftDowna[i][j];if(aRightUpaLeftDown)aList.push_back({r,c});}}// 输出 HcoutH\n;for(autop:hList)coutp.first p.second\n;// 输出 VcoutV\n;for(autop:vList)coutp.first p.second\n;// 输出 DcoutD\n;for(autop:dList)coutp.first p.second\n;// 输出 AcoutA\n;for(autop:aList)coutp.first p.second\n;}return0;}总结本题的核心是暴力模拟由于数据规模较小直接枚举每个格子并计算四个方向的和即可。解题时注意边界处理超出城市范围视为000以及输出格式中的顺序和空行要求无额外空行。此类题目通常不需要优化但需仔细实现累加逻辑避免重复计算或下标越界。技巧提炼当NNN较小时暴力枚举往往是最直接且可靠的解法注意利用循环的边界条件自然处理“外部为零”的情况无需额外填充。