【LightOJ】1122 - Digit Count（bfs）

点击打开题目

1122 - Digit Count

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.

Note

For the first case the valid integers are

11

13

31

33

66

结果是问有几个符合的结果，那么跑一遍bfs就行了，数据很小，暴力也可以过。

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define LL long long
#define PI acos(-1.0)
int n,k;
int num[15];
int ans;
void bfs(int x,int m)
{
	if (m == k)
	{
		ans++;
		return;
	}
	for (int i = 1 ; i <= n ; i++)
	{
		if (abs(num[i] - x) <= 2)
			bfs(num[i],m+1);
	}
}
int main()
{
	int u;
	int Case = 1;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d %d",&n,&k);
		for (int i = 1 ; i <= n ; i++)
			scanf ("%d",&num[i]);
		ans = 0;
		for (int i = 1 ; i <= n ; i++)
			bfs(num[i],1);
		printf ("Case %d: ",Case++);
		printf ("%d\n",ans);
	}
	return 0;
}