自动搬运

查看原文

来自洛谷，原作者为

	piske **

搬运于2025-08-24 23:11:43，当前版本为作者最后更新于2025-03-25 23:19:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[GESP202503 七级] 图上移动

思路：

遍历每一个点为起点，用深搜来找到每一步可以到达的点。并且使用数组存储防止重复访问。

#include <bits/stdc++.h>
using namespace std;
int vis[510][25];  //vis（i，j）表示第i个节点是否在第j步被访问过
int n,m,k;
vector<int> g[510];
void dfs(int u,int step){
	if(vis[u][step]==1)	   //防止重复访问
		return ;
	vis[u][step]=1;
	if(step==k)
		return ;
	step++;
	for(int i=0;i<g[u].size( );i++)
		dfs(g[u][i],step); //遍历所有路径
}
int main( ){
	cin>>n>>m>>k;
	for(int j=0;j<m;j++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v); //存图
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			for(int kk=0;kk<=k;kk++)
				vis[j][kk]=0; //初始化
		dfs(i,0); //以每个点为起点dfs
		for(int j=1;j<=k;j++){
			int ans=0;
			for(int kk=1;kk<=n;kk++)
				ans+=vis[kk][j]; //找到第j步可以访问的点的个数
			cout<<ans<<" ";
		}
		cout<<endl;
	}
最坏时间复杂度O（N*N*K）   （n轮dfs，每一轮最多访问N*K次节点）
	return 0;
}