Granny's Bike

http://acm.zju.edu.cn/show_problem.php?pid=1798

Time limit: 1 Seconds

Memory limit: 32768K

Most days Granny rides her bike around town to do errands, visit, have a cup of coffee, and so on. She enjoys riding her bike and wants to avoid passing the same place twice to add to the interest of the ride. So, each day she draws a map of the places to be visited, with lines connecting those near each other, and sees if she can visit them all and return home without passing a place more than once. Some days she finds she can do this and other days she finds she can't. For example, for the map on the left, Granny can visit every place and return home without passing any place twice, but she can't do it for the map on the right.

She turns to you to write a program to help her.

1. Input

There will be multiple test cases for this problem. Each test case will have input on multiple lines. The first line will contain the integer n (< 10) noting the number of places Granny wants to visit that day. These will be numbered 1 through n and Granny's house will be numbered 0. The next n lines will be a list of those places near each spot. The first line will be a list of places with a direct route from place 1. The second line will be a list of places with a direct route from place 2, and so on. You may assume that if place i has a direct route to place j, then there is a direct route the other direction also. A line containing 0 will follow the last test case.

2. Output

For each test case, print one line of the form:

Case m: Granny can make the circuit.

or

Case m: Granny can not make the circuit.

as appropriate. Here, m is the number of the test case, starting at 1.

3. Sample Input

5
0 2 5
0 1 3
2 4
0 3 5
1 4
4
0 2 3 4
1 3
1 2
0 1
0

4. Sample Output

Case 1: Granny can make the circuit.
Case 2: Granny can not make the circuit.

Problem Source: East Central North America 2003, Practice

   1 //2007-01-10 23:51:39 Accepted 1798 C++ 00:00.00 436K 
   2 //DFS
   3 //writen by 曹高挺
   4 #include <stdio.h>
   5 #include <string.h>
   6 
   7 bool map[10][10];
   8 bool path[10];
   9 int n;
  10 
  11 bool Travel(int from, int rest){
  12         //从from点开始DFS，剩余rest个点（包括from点）
  13         path[from] = true;
  14         rest --;
  15         if( rest == 0 ){//遍历完所有点，查看是否有到0点的路径
  16                 if( map[from][0] ){
  17                         return true;
  18                 }
  19         }
  20 
  21         int i;
  22         for(i=1; i<=n; i++){
  23                 if(!path[i] && map[from][i] && Travel(i, rest)){
  24                         return true;
  25                 }
  26         }
  27         rest ++;
  28         path[from] = false;
  29         return false;
  30 }
  31 
  32 bool GetInfo(){
  33         int i, tem;
  34         char c;
  35         scanf("%d", &n);
  36         if( !n )        return false;
  37         memset(map, false, sizeof(bool)*10*10);
  38         for(i=1; i<=n; i++){
  39                 do{
  40                         scanf("%d", &tem);
  41                         map[i][tem] = true;
  42                 }while( (c=getchar())!='\n' );
  43         }
  44         for(i=1; i<=n; i++){
  45                 map[0][i] = map[i][0];
  46         }
  47         return true;
  48 }
  49 
  50 int main(){
  51         int k = 0;
  52         while( GetInfo() ){
  53                 printf("Case %d: ", ++k);
  54                 memset(path, false, sizeof(bool)*10);
  55                 if( Travel(0, n+1) ){
  56                         printf("Granny can make the circuit.\n");
  57                 }
  58                 else{
  59                         printf("Granny can not make the circuit.\n");
  60                 }
  61         }//end of one case
  62 
  63         return 1;
  64 }