ACM之跳骚---ShinePans

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 

两个整数N和M(N <= 15 , M <= 100000000)。

可以完成任务的卡片数。

2 4

12

这12张卡片分别是： 
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4), 
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4) 

参考了下网上的解法,发现对逻辑的需求还是非常高的!自己能力还不足

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>  //system(); 这个指令需要用到此头文件
#include <ctype.h> //toupper要用到
#include <malloc.h> //在内存管理时用到的头文件
#include <string.h>  //字符串的头文件
#include <math.h>  //数学运算

int m = 0, n = 0, c[1000] = { NULL }, position = 0, count_can = 0;

bool jump(int x[])
{
	int temp1[1000] = { NULL }, temp2[1000] = { NULL };
	for (int i = 0; x[i] != NULL; i++)
	{
		if (x[i] == 1)
			return(true);
		temp1[i] = x[i];
	}
	int l = 1, s = 0;
	do{
		s = 0;
		if (l == 1)
		{

			for (int i = 0; temp1[i] != NULL; i++)
			{
				for (int j = i + 1; temp1[j] != NULL; j++)
				{

					if (fabs(temp1[i] - temp1[j]) == 1)
					{
						return(true);
					}
					if (temp1[i] - temp1[j] != 0)
					{
						temp2[s] = (int)fabs(temp1[i] - temp1[j]);
						s++;
					}
				}
				temp1[i] = 0;
			}
			l = 2;
		}
		else
		{

			for (int i = 0; temp2[i] != NULL; i++)
			{
				for (int j = i + 1; temp2[j] != NULL; j++)
				{
					if (fabs(temp2[i] - temp2[j]) == 1)
					{
						return(true);
					}
					if (temp2[i] - temp2[j] != 0)
					{
						temp1[s] = (int)fabs(temp2[i] - temp2[j]);
						s++;
					}
				}
				temp2[i] = 0;
			}
			l = 1;
		}

	} while (s != 0);
	return(false);

}
void card(int depth)
{
	if (depth == m)
	{
		c[m] = n;
		if (jump(c) == true)
		{
			count_can++;
		}
		return;
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			c[depth] = i;
			depth++;
			card(depth);
			depth--;
		}
		return;
	}
}
void main()
{
	scanf("%d%d", &m, &n);
	card(0);
	printf("%d\n", count_can);
}