代码编织梦想

最近小明喜欢上了散步。小明住在南山校区,他发现南山校区有n个景点(从1到n进行编号)很值得观赏,比如竹林舞步,小河夕阳等。小明不想错过每个景点,但又不想在一次散步过程中经过任意一个景点超过一次。小明的散步方案要求是从住所(设编号为0)出发,经过每个景点有且仅有一次,最后回到住所。你能告诉他满足要求的方案总数是多少吗?

【输入格式:】

首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据首先输入1个整数n(1≤n<10),然后有n行输入。第i行先输入一个整数mi(1≤mi≤n),然后是mi个整数,表示从景点i所能直达的景点(也可以是住所)编号。当然,若景点1能直达景点2,则景点2同样也能直达景点1。

【输出格式:】

对于每组测试,在一行上输出满足小明的散步方案要求的方案总数。

输入样例:

3

5

3 0 2 5

3 0 1 3

2 2 4

3 0 3 5

2 1 4

4

4 0 2 3 4

2 1 3

2 1 2

2 0 1

9

2 0 2

2 1 3

2 2 4

2 3 5

2 4 6

3 5 7 9

3 0 6 8

2 7 9

2 0 8

输出样例:

2

0

4

设计思想:利用DFS的方法每次都遍历他走过的路径看是否符合题目要求,如果不符合则用回溯法回溯。

#include<stdio.h>
#include<string.h>
int s[10][10],a[11],b[10];
int n,t,g;

void idfs(int k);
int main()
{int j,i,m,k,z;
memset(b,0,sizeof(b));
scanf("%d",&n);
z=n;
while(n>0)
{scanf("%d",&t);

memset(a,-1,sizeof(a));
memset(s,-1,sizeof(s));

for(i=1;i<=t;i++)
{scanf("%d",&m);
for(j=1;j<=m;j++)
{scanf("%d",&k);
s[k][i]=1;
s[i][k]=1;}
}
n--;

g=0;
idfs(0);
}

for(i=z-1;i>-1;i--)
printf("%d\n",b[i]);
}
void idfs(int k)
{int i,j;
	if(g==t&&s[0][k]==1)
{b[n]=b[n]+1;
return;}
	
for(j=1;j<=t;j++)
{if(s[k][j]==1 && a[j]==-1)
{a[j]=1;
g++;
idfs(j);
g--;
a[j]=-1;

}
	}}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_69749315/article/details/129678656

java《图书管理系统》练习_基于java的图书管理系统的题-爱代码爱编程

学习目录 书的对象(book) Book 书 BookList 书架 系统功能(operations)