GESP 题解库 / 7 级题解 / [GESP样题 七级] 迷宫统计 · 第 22 / 24 题
GESP样题 七级 · P10265 · 简单

迷宫统计

邻接矩阵里:第 m 行 1 的个数是"出",第 m 列 1 的个数是"入",两者相加即答案。

🏛️
n ≤ 1000
迷宫数量(矩阵规模)
🔢
int 足够
答案最大 2n = 2000
⚡
O(n²)
时间复杂度(读入主导)
🎯
行 = 出 / 列 = 入
邻接矩阵读法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

题目来源:[GESP样题 七级] 迷宫统计(洛谷 P10265)。

幻想大陆上有 n 个迷宫,编号 1 ~ n。有的迷宫之间可以直接往返,有的可以走到别的迷宫、但走不回来。小杨决定从 m 号迷宫出发,需要统计:m 号迷宫可以直接到达其他迷宫有多少、有多少迷宫可以直接到达 m 号迷宫,以及这两个数的和。

注意:对于任意 i(1 ≤ i ≤ n),i 号迷宫总可以直接到达自身。

输入格式:第一行两个整数 n 和 m;接下来 n 行,每行 n 个整数,第 i 行第 j 列的整数为 1 表示能从 i 号迷宫直接到达 j 号迷宫,为 0 表示不能。

输出格式:一行输出空格分隔的三个整数,依次是"m 可以直接到达的迷宫数"、"能直接到达 m 的迷宫数"、"两者的总和"。

💡
人话翻译:题目给的就是一张邻接矩阵。数"m 能直达谁"=数矩阵第 m 行里有多少个 1;数"谁能直达 m"=数第 m 列里有多少个 1;最后把两个数相加。
口诀:行 = 出发,列 = 到达。再牢记"每行每列对角线上的那个 1 代表自己能到自己",这题就吃透了。

🔍 关键词提取

邻接矩阵出度 / 入度只统计"直接"到达对角线计入O(n²)

已知条件

项目说明
输入第一行 n、m;随后 n 行 n 列的 0/1 矩阵
输出出 入 和 三个整数,空格分隔、顺序固定
数据范围1 ≤ m ≤ n ≤ 1000
矩阵含义a[i][j] = 1 ⟺ i 号能直接到达 j 号
特殊约定a[i][i] = 1:每个迷宫总能直接到达自身
子任务n ≤ 10(30 分)、n ≤ 100(30 分)、n ≤ 1000(40 分)

需要解决的问题

02
思维导图
整理解题思路的全貌
🏛️ 行 = 出,列 = 入
🧠 题意拆解
两个方向要分清:m → 别人、别人 → m
只统计"直接到达"(走一条边)
a[i][i] = 1:自己能到自己
输出顺序固定:出、入、和
📐 矩阵读法
第 m 行 a[m][1..n]:1 的个数 = m 的出度
第 m 列 a[1..n][m]:1 的个数 = m 的入度
行、列两个方向互不影响
答案 = 出 + 入
⚡ 复杂度
读入矩阵 O(n²) = 10⁶
数一行 + 数一列只有 O(n)
总复杂度 O(n²),瓶颈在读入
int 足够,最大答案 2n
⚠️ 易错点
行列搞反(最致命)
把输出顺序写成"入 出 和"
漏掉对角线上的自己
把"直接"当成"可达"而写了 BFS
03
样例手算推导
样例 1 的完整推演 + 两个极端规模自检

🧮 样例 1:n = 6,m = 4,输出 3 3 6

先把样例的邻接矩阵摆出来:行号在最左边,列号在最上面。

迷宫123456
1110100
2011000
3101001
4001101
5000110
6100011

目标是 4 号迷宫,所以只看第 4 行(数出)和第 4 列(数入)。

1
第 4 行:4 号能直接到达谁

第 4 行 = 0 0 1 1 0 1

为 1 的是第 3、4、6 列

所以 4 号能直达 3、4、6 号迷宫 —— 共 3 个

其中第 4 个 1 就是"4 能到达自己"

✅ 出 = 3

2
第 4 列:谁能直接到达 4 号

第 4 列自上而下 = 1 0 0 1 1 0

为 1 的是第 1、4、5 行

所以 1、4、5 号能直达 4 号迷宫 —— 共 3 个

其中第 4 个 1 同样是"自己到达自己"

✅ 入 = 3

3
求和并按要求顺序输出

3 + 3 = 6

按"出、入、和"的顺序打印

✅ 3 3 6(与样例一致)

🔑
4 号迷宫"自己那一票"被算了两次:一次记在行里(4 能到达 4),一次记在列里(4 到达 4)。
这是题目明确约定 a[i][i] = 1 的必然结果,不是重复计数,千万不要"去重"。

🧮 两个极端规模的自检

只想着"到达别的迷宫"的人,很容易把最小规模做成 0 0 0;只想着"只数别的迷宫"的人,又容易在全 1 矩阵上翻车。这两种极端都要亲手算一遍。

情形矩阵第 m 行 1 的个数第 m 列 1 的个数输出
n = 1,m = 111(自己)1(自己)1 1 2
n = 3,m = 2,只有对角线为 11 0 0 / 0 1 0 / 0 0 11(自己)1(自己)1 1 2
n = 2,m = 1,矩阵 1 1 / 0 11 1 / 0 12(1 号、2 号)1(1 号自己)2 1 3
n = 4,m = 4,全 1 矩阵四行都是 1 1 1 1444 4 8
⚠️
注意"只有对角线为 1"的情形:此时每个迷宫谁也到不了,只能到达自己,答案是 1 1 2 而不是 0 0 0。
反过来,全 1 矩阵时 n = 4、m = 4 的答案是 4 4 8:4 号能直达全部 4 个迷宫,也被全部 4 个迷宫直达。把这两个极端都算过,才能确认自己对"自身计入"和"输出顺序"没理解错。
04
解法对比
直接数行列 vs 搜索可达 / 传递闭包

⚔️ 解法对比

🟢 直接数第 m 行与第 m 列(推荐) 推荐

读完矩阵后,扫第 m 行得到"出"、扫第 m 列得到"入"

  • 读入 O(n²),统计只要 O(n)
  • n = 1000 时约 10⁶ 次读入,瞬间完成
  • 核心代码只有 5 行,几乎不可能写错
  • 完全贴合"直接到达"的字面含义
💡
为什么这样就够了:题目问的"直接到达"就是矩阵里的一条边,第 m 行把"从 m 出发的一条边"列全了,第 m 列把"指向 m 的一条边"列全了,不需要任何图搜索。

🟠 BFS / DFS 求可达

从 m 出发搜索,统计能走到的迷宫数

  • 复杂度也是 O(n²)(读入主导)
  • 代码约 30 行
  • 但把"多步可达"当成了"直接到达"
  • 答案偏大,属于误解题意
⚠️
对比一下就清楚了:样例里 4 号"直接到达"的只有 3、4、6 三个;但若改成"可达",从 3 还能走到 1、6,结果就完全不同了。题目里"直接"两个字是硬约束,读题必须逐字看。

📈 性能对比

方案复杂度代码量
直接数行列(正解)O(n²) 读入 + O(n) 统计约 5 行
BFS / DFS 求可达O(n²)约 30 行(而且题意错了)
Floyd 传递闭包O(n³) = 10⁹❌ 超时
05
算法流程图
读矩阵 → 数第 m 行 → 数第 m 列 → 输出三数
开始读入 n、m读入 n × n 的 0/1 邻接矩阵 a统计第 m 行:out = 该行中 1 的个数(m 能直达谁)统计第 m 列:in = 该列中 1 的个数(谁能直达 m)检查对角线 a[m][m] 是不是 1是 1 ✓说明"自己"被同时算进 out 和 in(正是题目要求)不是 1 ✗与题目约定不符,属异常数据,可忽略输出 out、in、out + in(空格分隔)
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏛️ 迷宫进出统计器

第一行输入 n 和 m,随后 n 行每行 n 个 0/1(代表邻接矩阵)。程序会数出第 m 行的 1、第 m 列的 1 以及它们的和。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(直接数第 m 行与第 m 列)

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

int a[1005][1005];                 // 邻接矩阵,开全局避免爆栈

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    int outDeg = 0, inDeg = 0;
    for (int j = 1; j <= n; j++)       // 第 m 行:m 能直达谁
        if (a[m][j] == 1) outDeg++;

    for (int i = 1; i <= n; i++)       // 第 m 列:谁能直达 m
        if (a[i][m] == 1) inDeg++;

    printf("%d %d %d\n", outDeg, inDeg, outDeg + inDeg);
    return 0;
}
🔑
两个循环的下标正好是"交换"的:数行时用 a[m][j](m 固定、j 变化),数列时用 a[i][m](i 变化、m 固定)。
只要记住"行 = 出、列 = 入",这两个循环就不可能写反。

📖 关键几行怎么看

代码作用为什么这样写
int a[1005][1005];存矩阵n ≤ 1000,1005² 个 int ≈ 4 MB;开全局避免放在栈上爆栈
a[m][j]第 m 行行 = 出发:统计 m 能直达哪些迷宫
a[i][m]第 m 列列 = 到达:统计哪些迷宫能直达 m
printf("%d %d %d", outDeg, inDeg, ...)输出顺序题目要求顺序是出、入、和,顺序换了就错
a[i][i] 恒为 1自身计入对角线让 outDeg、inDeg 各自至少为 1
⚠️
四个坑:① 把行列搞反——这是本题最常见的失分点;② 输出顺序写成"入 出 和";③ 把"直接到达"做成"多步可达"(写 BFS / Floyd);④ 把 1000 × 1000 的数组开在 main 里(约 4 MB 栈空间,可能直接崩溃)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6 4
1 1 0 1 0 0
0 1 1 0 0 0
1 0 1 0 0 1
0 0 1 1 0 1
0 0 0 1 1 0
1 0 0 0 1 1
3 3 6题面样例 1
1 1
1
1 1 2最小规模:只有自己,"1 1 2"而不是"0 0 0"
3 2
1 0 0
0 1 0
0 0 1
1 1 2只有对角线为 1:谁也到不了别人
2 1
1 1
0 1
2 1 31 号能直达 1、2 两个;只有 1 号(自己)能直达 1 号
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4 4 8全 1 矩阵:4 号直达全部 4 个,也被全部 4 个直达
5 3
1 0 1 0 0
0 1 0 0 0
1 1 1 0 1
0 0 1 1 0
0 0 0 0 1
4 3 7第 3 行有 4 个 1、第 3 列有 3 个 1,注意行列入不相同
✅
自查清单:① 数的是第 m 行和第 m 列吗?② 输出顺序是"出、入、和"吗?③ 只统计"直接"(一条边)吗?④ n = 1 时输出的是 1 1 2 吗?⑤ 矩阵开成全局数组了吗?

🚨 易错点清单

⚠️
行、列搞反:"m 能直达谁"看第 m 行,"谁能直达 m"看第 m 列。两个循环的固定下标一个是 m(行)、一个也是 m(列),但变化的那一维位置不同,务必写清 a[m][j] 与 a[i][m]。
⚠️
输出顺序写错:题目要求先出、后入、再和,三数之间用空格分隔。
⚠️
把"直接"做成"可达":题目只统计走一条边就到的迷宫,写 BFS / Floyd 会把需要中转的迷宫也算进来。
⚠️
漏掉对角线:a[i][i] = 1 是题目约定,第 m 行/第 m 列里的"自己"必须计入,漏掉就会少 1(甚至少 2)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n²)
n 最大
1000
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

邻接矩阵 1005 × 1005 个 int ≈ 4 MB,远低于 256 MB 内存限制;开成全局数组即可。

✅ 约 100 万次操作,1 秒时限内不到 1 毫秒。本题真正的瓶颈是读入矩阵,统计部分只有 O(n)——所以哪怕把统计写成 O(n²) 也毫无影响。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 行 = 出,列 = 入
int outDeg = 0, inDeg = 0;
for (int j = 1; j <= n; j++) if (a[m][j]) outDeg++;   // 第 m 行
for (int i = 1; i <= n; i++) if (a[i][m]) inDeg++;    // 第 m 列

// ② 更省事:读入时顺手把"度"统计好,事后不必再扫两遍
int oDeg[1005] = {0}, iDeg[1005] = {0};
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        scanf("%d", &a[i][j]);
        if (a[i][j] == 1) { oDeg[i]++; iDeg[j]++; }   // 一条边 i -> j 的贡献
    }
// 此时答案就是 oDeg[m]、iDeg[m]、oDeg[m] + iDeg[m]

// ③ 输入共 n² = 10⁶ 个数字,用 scanf 足够快(不加 sync_with_stdio 的 cin 会慢很多)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
邻接矩阵读法行 = 出发、列 = 到达所有"看矩阵数关系"的入门图论题
度计数一条边 u → v 让 outDeg[u]++、inDeg[v]++拓扑排序、欧拉路径、网络流建图
只统计"直接"关系只扫一层,不做多步搜索单步关系统计题(别过度设计)
输入规模估算n² = 10⁶,判断该用 O(n²) 还是更快所有题的第一步:先算运算量
🌟
思考题:如果把题目改成"m 号迷宫能间接到达(允许中转任意多次)的迷宫有多少个",该怎么做?(提示:从 m 出发做一次 BFS/DFS,数一数能访问到多少个点即可;也可以对矩阵做传递闭包,但那是 O(n³),n = 1000 时不可行。
注意:"直接到达"与"可达"只差一个词,做法却从 5 行变成 30 行——读题时区分这两个词,是图论题的第一道关。)