本文共 1070 字，大约阅读时间需要 3 分钟。

打卡 day4
先拿一道题练练手，一会儿再开新题，拒绝水题。
这题好像挺简单的，输出全路径，就是深搜搜完一条路径之后不要退，接着搜第二条，直到所有路径都搜完为止。
然后就是一个被问过两遍，自己一直也没有太清楚的，就是：

vis[next]=1;dfs(next,idx+1);vis[next]=0;

到底什么时候需要回溯，为什么有的题不用回溯也结果正确，现在知道是测试数据弱，或者说题面说保证只有一条路径。vis数组再次标记为0代表这个点没有访问过，如果不回溯，记录全路径，不同路径之间会发生“撞车”，我用这个点，另一条路径也用这个点，但是因为我走过了这个点，所以该点已经被标记为访问过，其它路再来走的话，会视为访问过，但其实没有。但是回溯之后表示我用完了这个点，我有把我的访问擦除，让其它路也能经过这个点。

AC代码：

#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<string>#include<cstring>#include<vector>using namespace std;int maps[22][3];int p[22];int vis[22];int n;int cnt;void dfs(int val,int idx){   	p[idx]=val;	for(int i=0;i<3;i++){   		int next=maps[val][i];		if(idx==19&&next==n){   			printf("%d:  ",cnt++);			for(int j=0;j<20;j++){   				printf("%d ",p[j]);			}			printf("%d\n",next);		}		if(!vis[next]){   			vis[next]=1;			dfs(next,idx+1);			vis[next]=0;		}	}}int main(){   	int a,b,c;	for(int i=1;i<=20;i++){   		scanf("%d%d%d",&maps[i][0],&maps[i][1],&maps[i][2]);	}	while(scanf("%d",&n)){   		if(n==0) break;		memset(vis,0,sizeof(vis));		vis[n]=1;		cnt=1;		dfs(n,0);	}	return 0;}

转载地址：http://lhdr.baihongyu.com/