UVa 11620 City of Egocentrics-开发者社区

题目描述

在一个N×NN \times NN×N的网格城市中，每个格子居住着若干人（0∼100000 \sim 100000∼10000）。存在四种类型的“自我中心者”：

HHH型：该格子所在行中，左侧所有格子的人数总和等于右侧所有格子的人数总和。
VVV型：该格子所在列中，上方所有格子的人数总和等于下方所有格子的人数总和。
DDD型：该格子所在主对角线（左上‑右下）上，左上方向所有格子的人数总和等于右下方向所有格子的人数总和。
AAA型：该格子所在反对角线（右上‑左下）上，右上方向所有格子的人数总和等于左下方向所有格子的人数总和。

对于边界格子，超出城市范围的方向视为人数为000。

一个格子可能同时满足多种类型。现需按顺序列出所有满足HHH、VVV、DDD、AAA条件的格子坐标，按行优先输出。

输入格式

第一行为测试用例数TTT。
每个测试用例第一行为整数NNN（N≤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)。当N=100N = 100N=100时，约10610^6106次操作，完全可以接受。因此无需复杂的数据结构，直接模拟即可。

需要注意边界处理：当格子位于边界时，超出城市方向视为人数为000，这可以在循环累加时通过越界判断自然实现。

解题思路

读入数据：存储矩阵a[N][N]。
遍历每个格子(r, c)（0≤r,c<N0 \le r, c < N0≤r,c<N）：
- HHH型：计算该行第ccc列左侧所有格子的和leftSum，以及右侧所有格子的和rightSum，若相等则记录坐标。
- VVV型：计算该列第rrr行上方所有格子的和upSum，以及下方所有格子的和downSum，若相等则记录。
- DDD型：沿主对角线方向，向左上累加（r-1, c-1直至越界）得到dLeftUp；向右下累加（r+1, c+1直至越界）得到dRightDown，比较。
- AAA型：沿反对角线方向，向右上累加（r-1, c+1直至越界）得到aRightUp；向左下累加（r+1, c-1直至越界）得到aLeftDown，比较。
将满足条件的坐标分别存入四个列表hList、vList、dList、aList。由于遍历顺序就是行优先，因此列表自然按行优先排序。
输出：按顺序输出HHH、VVV、DDD、AAA，每组先输出字母行，然后逐行输出坐标；若某列表为空，则仅输出字母行。

复杂度分析

时间复杂度：每个格子需进行四次累加，每次累加最多遍历NNN个元素，故总操作次数约为4×N2×N=O(N3)4 \times N^2 \times N = O(N^3)4×N2×N=O(N3)。N=100N=100N=100时约为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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intN;cin>>N;vector<vector<int>>a(N,vector<int>(N));for(inti=0;i<N;++i)for(intj=0;j<N;++j)cin>>a[i][j];vector<pair<int,int>>hList,vList,dList,aList;for(intr=0;r<N;++r){for(intc=0;c<N;++c){// 计算 HintleftSum=0,rightSum=0;for(inti=0;i<c;++i)leftSum+=a[r][i];for(inti=c+1;i<N;++i)rightSum+=a[r][i];if(leftSum==rightSum)hList.push_back({r,c});// 计算 VintupSum=0,downSum=0;for(inti=0;i<r;++i)upSum+=a[i][c];for(inti=r+1;i<N;++i)downSum+=a[i][c];if(upSum==downSum)vList.push_back({r,c});// 计算 D（主对角线）intdLeftUp=0,dRightDown=0;for(inti=r-1,j=c-1;i>=0&&j>=0;--i,--j)dLeftUp+=a[i][j];for(inti=r+1,j=c+1;i<N&&j<N;++i,++j)dRightDown+=a[i][j];if(dLeftUp==dRightDown)dList.push_back({r,c});// 计算 A（反对角线）intaRightUp=0,aLeftDown=0;for(inti=r-1,j=c+1;i>=0&&j<N;--i,++j)aRightUp+=a[i][j];for(inti=r+1,j=c-1;i<N&&j>=0;++i,--j)aLeftDown+=a[i][j];if(aRightUp==aLeftDown)aList.push_back({r,c});}}// 输出 Hcout<<"H\n";for(auto&p:hList)cout<<p.first<<" "<<p.second<<"\n";// 输出 Vcout<<"V\n";for(auto&p:vList)cout<<p.first<<" "<<p.second<<"\n";// 输出 Dcout<<"D\n";for(auto&p:dList)cout<<p.first<<" "<<p.second<<"\n";// 输出 Acout<<"A\n";for(auto&p:aList)cout<<p.first<<" "<<p.second<<"\n";}return0;}