题解：P11964 [GESP202503 七级] 图上移动

· · 题解

[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;
}