HDU 2181哈密顿绕行世界问题（简单DFS）

- 日理万妓 2024-02-17 19:05 68阅读 0赞

### 哈密顿绕行世界问题 ###

[HDU - 2181 ][HDU - 2181]

#include<cstdio>
    int a[20+2][3+1];
    int path[20+2];
    int flag; 
    int m;
    void dfs(int t,int count){
    	if(t==m && count==20){
    		path[count]=m;
    		printf("%d:  %d",flag++,path[0]);
    		for(int i=1;i<21;i++)printf(" %d",path[i]);
    		printf("\n");
    		return ;
    	}
    	for(int i=0;i<count;i++)if(t==path[i])return;  //如果出现过不能再出现 
    	path[count]=t;
    	for(int i=0;i<3;i++)dfs(a[t][i],count+1);
    }
    int main(){
    	for(int i=1;i<=20;i++)scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    	while(scanf("%d",&m)==1 && m){
    	flag=1;
    	path[0]=m;
    	for(int i=0;i<3;i++){
    		dfs(a[m][i],1);
    	}
    }
    	return 0;
    }

解法二：

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector<int> g[20+2];
    int vist[20+2];
    int path[20+2];
    int start;
    
    void dfs(int m,int cnt){
    	if(cnt == 21){
    		printf("%d: ",start);
    		for(int i = 1; i <= 21; i++)
    		printf(" %d",path[i]);
    		printf("\n");
    		start++;
    		return ;
    	}
    	
    	for(int i = 0; i < g[m].size(); i++){
    		if(!vist[g[m][i]]){
    			vist[g[m][i]] = 1;
    			path[cnt+1] = g[m][i];
    			dfs(g[m][i],cnt+1); 
    			vist[g[m][i]] = 0;
    		}
    		
    		if((g[m][i]==path[1]) && cnt==20){  //最后要回到起点 
    			path[cnt+1] = g[m][i];
    			dfs(g[m][i],cnt+1); 
    		}
    	}
    }
    
    int main(){
        for(int i = 1; i <= 20; i++){
        	int a,b,c;
        	scanf("%d%d%d",&a,&b,&c);
        	g[i].push_back(a);
        	g[i].push_back(b);
        	g[i].push_back(c);
    	}	
    	
    	int m;
    	while(scanf("%d",&m) == 1 && m){
    		memset(vist,0,sizeof(vist));
    		start = 1;
    		path[1] = m;
    		vist[m] = 1;
    		dfs(m,1);
    	}
    	return 0;
    }

[HDU - 2181]: https://vjudge.net/problem/28243/origin