hdu 5641 King's Phone

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5641

题目类型：水题

题目思路：将点x到点y所需要跨过的点存入mark[x][y]中(无需跨过其它点存0)，然后按照题目给的路径逐一判断是否可走，得出结果。

需要判断的：

1.给出的点是否在1～9之间

2.点的数量n是否在4～9之间

3.有没有重复的点

4.两点之间(x-->y)是否需要跨过第三点(z)，该点(z)是否已经走过

测试样例(基本考虑了所有情况)：

10
4 1 3 6 2
4 6 2 1 3
4 8 1 6 7
6 2 1 2 3 5 7
6 1 5 8 2 6 7
5 4 2 8 5 6
5 12 3 4 5 6
7 0 1 2 3 4 5 6
3 1 5 9
9 1 5 9 4 2 6 3 7 8

1.invalid
2.valid
3.valid
4.invalid
5.valid
6.invalid
7.invalid
8.invalid
9.invalid
10.valid

实现代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 //若从i->j 必须经过其它点，存入mark[i][j]中，否则mark[i][j]为0
 6 int mark[10][10] = {
 7         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
 8         { 0, 0, 0, 2, 0, 0, 0, 4, 0, 5 },
 9         { 0, 0, 0, 0, 0, 0, 0, 0, 5, 0 },
10         { 0, 2, 0, 0, 0, 0, 0, 5, 0, 6 },
11         { 0, 0, 0, 0, 0, 0, 5, 0, 0, 0 },
12         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
13         { 0, 0, 0, 0, 5, 0, 0, 0, 0, 0 },
14         { 0, 4, 0, 5, 0, 0, 0, 0, 0, 8 },
15         { 0, 0, 5, 0, 0, 0, 0, 0, 0, 0 },
16         { 0, 5, 0, 6, 0, 0, 0, 8, 0, 0 }
17 };
18 
19 //a[]存走的路线
20 int a[10];
21 
22 //num[]统计各个点出现的次数
23 int num[10];
24 
25 //flag[]记录各个点是否被走过，0表示未走，1表示已走
26 int flag[10];
27 
28 int main()
29 {
30     int T;
31     int n;
32     int i, ans;
33     scanf("%d", &T);
34     while (T--)
35     {
36         scanf("%d", &n);
37         ans = 1;
38         memset(a, 0, sizeof(a));
39         memset(num, 0, sizeof(num));
40         memset(flag, 0, sizeof(flag));
41         for (i = 1; i <= n; i++)
42         {
43             scanf("%d", &a[i]);
44             if(a[i]<1 || a[i]>9)  //点是否在范围内
45                 ans = 0;
46         }
47         if(!ans)
48         {
49             printf("invalid
");
50             continue;
51         }
52         for(i=1; i<=n; i++)
53             num[a[i]]++;
54         for (i = 1; i <= 9; i++) {
55             if (num[i] > 1)
56                 break;
57         }
58         if (n < 4 || n >9 || i<10)  //点的数量是否在范围内，各点是不是最多只有一个
59         {
60             printf("invalid
");
61             continue;
62         }
63         int x, y;
64         for (i = 1; i < n; i++)  //n个点会有n-1条线
65         {
66             x = a[i];
67             y = a[i + 1];
68             if ( (mark[x][y] != 0) && (flag[mark[x][y]] == 0) )
69             {
70                 ans = 0;  //如果x->y需要跨过点mark[x][y],而mark[x][y]未走过，则不可行
71                 break;
72             }
73             flag[x] = 1;
74         }
75         if (ans)
76             printf("valid
");
77         else
78             printf("invalid
");
79     }
80     return 0;
81 }