题目1531: One Day Tour In ZJU-白红宇

题目1531: One Day Tour In ZJU

阅读量：4104 次

发布时间：2019-05-25

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

题目描述

Xiao Ming's parents visit ZJU and Xiao Ming want to take them to look around the campus.They will start from the stone with two famous question raised by President Zhu Kezhen and end at largest dining room in Asia.They want to visit every place exactly once in ZJU's campus,including the stone and dining room.

输入

The input consists of multiple test cases.

The first line contains an integer n(n<=20),which means the number of place in ZJU's campus.We give numbers(from 1 to n to the places,especailly,1 means the stone with two famous question and n means the largest dining room.

The second line contains an integer m,which means the number of roads between two place.

Then follows m lines,each line contain two integer,which means there is a road between these two place.The road will not repeat more than one time.

输出

For each test case, you should output one line.If the path exists,you should output 1.Otherwise,you should output 0.

样例输入

5 4 1 2 1 3 1 4 2 5 6 6 1 3 3 2 1 2 3 4 4 5 5 6

样例输出

0 1

提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

来源

/**********************************   日期：2013-3-23*   作者：SJF0115*   题号: 题目1531: One Day Tour In ZJU*   来源：http://acmclub.com/problem.php?id=1531*   结果：AC*   来源：2013年浙江大学复试机试模拟题*   总结：**********************************/#include
   
    #include
    
     int n,m,ok;int vis[22],Map[22][22];//搜索，已经访问count个地方现在处于location点void DFS(int location,int count){	int i;	//已经全部访问完	if(count == n){		//到达目的地n		if(location == n){			ok = 1;		}		return;	}	//没有访问完，访问下一处	for(i = 1;i <= n;i++){		//i点没访问过且能访问则去i点		if(Map[location][i] == 1&& vis[i] == 0){			//标记i已经访问过			vis[i]=1;			//递归下一处			DFS(i,count+1);			if(ok == 1){				return;			}			//取消标记			vis[i] = 0;		}	}}//初始化void Init(){	int i,j,start,end;	//初始化地图	for(i = 1;i <= n;i++){		for(j = 1;j <= n;j++){			Map[i][j]=0;		}	}	//添加路况	for(i = 0;i < m;i++){		scanf("%d %d",&start,&end);		//end和start之间联通		Map[start][end]=1;		Map[end][start]=1;	}	memset(vis,0,sizeof(vis));	ok = 0;	//1为出发点	vis[1]=1;}int main(){	while(scanf("%d %d",&n,&m)!=EOF){		Init();		DFS(1,1);	    printf("%d\n",ok);	}	return 0;}

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

你可能感兴趣的文章