迷宫可达性统计问题详解
问题重述与深入理解
题目描述了一个由n个迷宫组成的系统，每个迷宫都有唯一编号（从1到n）。迷宫间的连接关系通过一个n×n的邻接矩阵表示，其中：
- 矩阵元素a[i][j] = 1表示存在从迷宫i到迷宫j的单向通道
- a[i][j] = 0表示没有直接通道
- 每个迷宫默认可以到达自身（即a[i][i] = 1）
具体任务要求：
- 统计从指定迷宫m出发能直接到达的迷宫数量（出度）
- 统计能直接到达迷宫m的迷宫数量（入度）
- 计算这两个数值的和
示例说明：假设有3个迷宫，邻接矩阵为：
1 1 0
0 1 1
1 0 1
对于m=2：
- 出度为2（可到达迷宫2和3）
- 入度为2（可被迷宫1和2到达）
- 总和为4
图论视角分析
从图论角度看，这个问题可以建模为有向图：
- 迷宫代表图的顶点
- 通道代表有向边
- 邻接矩阵是图的存储表示
关键概念：
- 出度：顶点m的出边数量，对应从m出发的直接可达迷宫数
- 入度：指向顶点m的边数量，对应可直接到达m的迷宫数
- 自环：每个顶点都有指向自身的边（a[i][i]=1）
动态规划解法深度解析
虽然本题可以直接统计行列解决，但动态规划思路可以扩展到更复杂的图可达性问题：
状态定义与转移
定义dp[k][i][j]表示通过前k个中间节点，i到j是否存在路径
状态转移方程：
dp[k][i][j] = dp[k-1][i][j] || (dp[k-1][i][k] && dp[k-1][k][j])
优化空间复杂度后：
dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j])
应用场景
这种动态规划方法（Floyd-Warshall算法）可以解决：
- 全源最短路径问题
- 传递闭包计算
- 复杂网络的可达性分析
完整代码解析与优化
基础实现分析
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10; // 最大支持1000个迷宫
bool a[maxn][maxn]; // 邻接矩阵存储
int n,m,ans1,ans2; // 迷宫数，起始迷宫，出度，入度int main(){cin>>n>>m;// 输入邻接矩阵for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>a[i][j];// 统计出度和入度for(int i=1;i<=n;i++){if(a[m][i]) ans1++; // 统计第m行if(a[i][m]) ans2++; // 统计第m列}cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
时间复杂度分析
- 输入阶段：O(n²) - 必须读取整个矩阵
- 统计阶段：O(n) - 只需遍历一行一列
- 总体复杂度：O(n²)
空间优化方案
对于稀疏图（通道较少的情况），可以采用：
- 邻接表存储
- 压缩稀疏行(CSR)格式
- 位矩阵存储
性能优化实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
bitset<maxn> a[maxn]; // 使用bitset节省空间int main(){ios::sync_with_stdio(false);cin.tie(0); // 加速IOint n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){bool x; cin>>x;a[i][j]=x;}// 使用bitset内置函数快速统计int ans1=a[m].count(), ans2=0;for(int i=1;i<=n;i++)ans2+=a[i][m];cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
优化点：
- 使用bitset减少内存占用
- 利用count()函数快速统计1的个数
- IO加速提高输入效率
边界情况与验证
需要考虑的特殊情况：
- 单个迷宫系统（n=1）
- 完全不连通的情况（只有自环）
- 完全连通的情况
- 最大规模测试（n=1000）
验证方法：
- 单元测试：针对各种边界条件设计测试用例
- 对拍测试：与朴素实现对比结果
- 性能测试：测试大规模输入时的运行时间
扩展应用场景
该算法的变种可以应用于：
- 社交网络分析（统计用户的关注/粉丝数）
- 交通网络的可达性分析
- 程序调用关系的统计分析
- 网页链接分析（计算入链和出链数量）
进阶思考题
- 如何统计间接可达的迷宫数量？（考虑路径长度限制）
- 如果通道有加权，如何计算最优路径？
- 在分布式环境下如何实现该算法？
- 如何实时更新并维护可达性统计？
迷宫可达性统计问题详解
问题重述与深入理解
题目描述了一个由n个迷宫组成的系统，每个迷宫都有唯一编号（从1到n）。迷宫间的连接关系通过一个n×n的邻接矩阵表示，其中：
- 矩阵元素a[i][j] = 1表示存在从迷宫i到迷宫j的单向通道
- a[i][j] = 0表示没有直接通道
- 每个迷宫默认可以到达自身（即a[i][i] = 1）
具体任务要求：
- 统计从指定迷宫m出发能直接到达的迷宫数量（出度）
- 统计能直接到达迷宫m的迷宫数量（入度）
- 计算这两个数值的和
示例说明：假设有3个迷宫，邻接矩阵为：
1 1 0
0 1 1
1 0 1
对于m=2：
- 出度为2（可到达迷宫2和3）
- 入度为2（可被迷宫1和2到达）
- 总和为4
图论视角分析
从图论角度看，这个问题可以建模为有向图：
- 迷宫代表图的顶点
- 通道代表有向边
- 邻接矩阵是图的存储表示
关键概念：
- 出度：顶点m的出边数量，对应从m出发的直接可达迷宫数
- 入度：指向顶点m的边数量，对应可直接到达m的迷宫数
- 自环：每个顶点都有指向自身的边（a[i][i]=1）
动态规划解法深度解析
虽然本题可以直接统计行列解决，但动态规划思路可以扩展到更复杂的图可达性问题：
状态定义与转移
定义dp[k][i][j]表示通过前k个中间节点，i到j是否存在路径
状态转移方程：
dp[k][i][j] = dp[k-1][i][j] || (dp[k-1][i][k] && dp[k-1][k][j])
优化空间复杂度后：
dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j])
应用场景
这种动态规划方法（Floyd-Warshall算法）可以解决：
- 全源最短路径问题
- 传递闭包计算
- 复杂网络的可达性分析
完整代码解析与优化
基础实现分析
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10; // 最大支持1000个迷宫
bool a[maxn][maxn]; // 邻接矩阵存储
int n,m,ans1,ans2; // 迷宫数，起始迷宫，出度，入度int main(){cin>>n>>m;// 输入邻接矩阵for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>a[i][j];// 统计出度和入度for(int i=1;i<=n;i++){if(a[m][i]) ans1++; // 统计第m行if(a[i][m]) ans2++; // 统计第m列}cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
时间复杂度分析
- 输入阶段：O(n²) - 必须读取整个矩阵
- 统计阶段：O(n) - 只需遍历一行一列
- 总体复杂度：O(n²)
空间优化方案
对于稀疏图（通道较少的情况），可以采用：
- 邻接表存储
- 压缩稀疏行(CSR)格式
- 位矩阵存储
性能优化实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
bitset<maxn> a[maxn]; // 使用bitset节省空间int main(){ios::sync_with_stdio(false);cin.tie(0); // 加速IOint n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){bool x; cin>>x;a[i][j]=x;}// 使用bitset内置函数快速统计int ans1=a[m].count(), ans2=0;for(int i=1;i<=n;i++)ans2+=a[i][m];cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
优化点：
- 使用bitset减少内存占用
- 利用count()函数快速统计1的个数
- IO加速提高输入效率
边界情况与验证
需要考虑的特殊情况：
- 单个迷宫系统（n=1）
- 完全不连通的情况（只有自环）
- 完全连通的情况
- 最大规模测试（n=1000）
验证方法：
- 单元测试：针对各种边界条件设计测试用例
- 对拍测试：与朴素实现对比结果
- 性能测试：测试大规模输入时的运行时间
扩展应用场景
该算法的变种可以应用于：
- 社交网络分析（统计用户的关注/粉丝数）
- 交通网络的可达性分析
- 程序调用关系的统计分析
- 网页链接分析（计算入链和出链数量）
进阶思考题
- 如何统计间接可达的迷宫数量？（考虑路径长度限制）
- 如果通道有加权，如何计算最优路径？
- 在分布式环境下如何实现该算法？
- 如何实时更新并维护可达性统计？
迷宫可达性统计问题详解
问题重述与深入理解
题目描述了一个由n个迷宫组成的系统，每个迷宫都有唯一编号（从1到n）。迷宫间的连接关系通过一个n×n的邻接矩阵表示，其中：
- 矩阵元素a[i][j] = 1表示存在从迷宫i到迷宫j的单向通道
- a[i][j] = 0表示没有直接通道
- 每个迷宫默认可以到达自身（即a[i][i] = 1）
具体任务要求：
- 统计从指定迷宫m出发能直接到达的迷宫数量（出度）
- 统计能直接到达迷宫m的迷宫数量（入度）
- 计算这两个数值的和
示例说明：假设有3个迷宫，邻接矩阵为：
1 1 0
0 1 1
1 0 1
对于m=2：
- 出度为2（可到达迷宫2和3）
- 入度为2（可被迷宫1和2到达）
- 总和为4
图论视角分析
从图论角度看，这个问题可以建模为有向图：
- 迷宫代表图的顶点
- 通道代表有向边
- 邻接矩阵是图的存储表示
关键概念：
- 出度：顶点m的出边数量，对应从m出发的直接可达迷宫数
- 入度：指向顶点m的边数量，对应可直接到达m的迷宫数
- 自环：每个顶点都有指向自身的边（a[i][i]=1）
动态规划解法深度解析
虽然本题可以直接统计行列解决，但动态规划思路可以扩展到更复杂的图可达性问题：
状态定义与转移
定义dp[k][i][j]表示通过前k个中间节点，i到j是否存在路径
状态转移方程：
dp[k][i][j] = dp[k-1][i][j] || (dp[k-1][i][k] && dp[k-1][k][j])
优化空间复杂度后：
dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j])
应用场景
这种动态规划方法（Floyd-Warshall算法）可以解决：
- 全源最短路径问题
- 传递闭包计算
- 复杂网络的可达性分析
完整代码解析与优化
基础实现分析
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10; // 最大支持1000个迷宫
bool a[maxn][maxn]; // 邻接矩阵存储
int n,m,ans1,ans2; // 迷宫数，起始迷宫，出度，入度int main(){cin>>n>>m;// 输入邻接矩阵for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>a[i][j];// 统计出度和入度for(int i=1;i<=n;i++){if(a[m][i]) ans1++; // 统计第m行if(a[i][m]) ans2++; // 统计第m列}cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
时间复杂度分析
- 输入阶段：O(n²) - 必须读取整个矩阵
- 统计阶段：O(n) - 只需遍历一行一列
- 总体复杂度：O(n²)
空间优化方案
对于稀疏图（通道较少的情况），可以采用：
- 邻接表存储
- 压缩稀疏行(CSR)格式
- 位矩阵存储
性能优化实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
bitset<maxn> a[maxn]; // 使用bitset节省空间int main(){ios::sync_with_stdio(false);cin.tie(0); // 加速IOint n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){bool x; cin>>x;a[i][j]=x;}// 使用bitset内置函数快速统计int ans1=a[m].count(), ans2=0;for(int i=1;i<=n;i++)ans2+=a[i][m];cout<<ans1<<' '<<ans2<<' '<<ans1+ans2;return 0;
}
优化点：
- 使用bitset减少内存占用
- 利用count()函数快速统计1的个数
- IO加速提高输入效率
边界情况与验证
需要考虑的特殊情况：
- 单个迷宫系统（n=1）
- 完全不连通的情况（只有自环）
- 完全连通的情况
- 最大规模测试（n=1000）
验证方法：
- 单元测试：针对各种边界条件设计测试用例
- 对拍测试：与朴素实现对比结果
- 性能测试：测试大规模输入时的运行时间
扩展应用场景
该算法的变种可以应用于：
- 社交网络分析（统计用户的关注/粉丝数）
- 交通网络的可达性分析
- 程序调用关系的统计分析
- 网页链接分析（计算入链和出链数量）
进阶思考题
- 如何统计间接可达的迷宫数量？（考虑路径长度限制）
- 如果通道有加权，如何计算最优路径？
- 在分布式环境下如何实现该算法？
- 如何实时更新并维护可达性统计？