题目链接:http://lightoj.com/volume_showproblem.php?problem=1122
Time Limit: 2 second(s) Memory Limit: 32 MB

Problem Description

Given a set of digits S, and an integer n, you have to find how many n-digit integers are there, which contain digits that belong to S and the difference between any two adjacent digits is not more than two.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case contains two integers, m (1 ≤ m < 10) and n (1 ≤ n ≤ 10). The next line will contain m integers (from 1 to 9) separated by spaces. These integers form the set S as described above. These integers will be distinct and given in ascending order.

Output

For each case, print the case number and the number of valid n-digit integers in a single line.

Sample Input

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

Output for Sample Input

Case 1: 5
Case 2: 9
Case 3: 9

Note

For the first case the valid integers are
11
13
31
33
66

Problem solving report:

Description: 给你m种数，要求使用这m种数组成n位整数，使得该数的每位和相邻位的数的差不超过2。
Problem solving: 数据较小，直接DFS就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
int n, m, spt[15];
int DFS(int u, int l) {
    if (l >= n)
        return 1;
    int ans = 0;
    for (int i = u - 2; i <= u + 2; i++)
        if (i >= 0 && i < m && abs(spt[u] - spt[i]) <= 2)
            ans += DFS(i, l + 1);
    return ans;
}
int main() {
    int t, ans, kase = 0;
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++)
            scanf("%d", &spt[i]);
        for (int i = 0; i < m; i++)
            ans += DFS(i, 1);
        printf("Case %d: %d\n", ++kase, ans);
    }
    return 0;
}