第二题 将1到9这9个数字分成三组，每组分别包含n、m、k个数字，满足条件 n+m+k=9。每个数字只能属于一个组。若使用每组中的数字能构建出至少一个完全平方数，则称这种划分方式是合法的。构建平方数时每个数字可以使用0次或1次。完全平方数是指可以表示为某个正整数的平方的数。题目要求计算有多少种这样的合法划分方式。

输入格式为一行，包含3个正整数n, m, k。```c

#include <stdio.h>
int ans = 0;//ans代表答案数目
int a[10][10];//标记每一组的每个数
int b[10] = {0,0,0,0,0,0,0,0,0,0};//标记1-9每个数字是否被标记
int g[4];//标记每个组的数字数目



int vaild(int g,int n)
{
	int c2 = 0, c3 = 0, c5 = 0, c6 = 0, c7 = 0;//标记是否有25，36，576
	int result=0;
	for (int j = 1; j <= n; j++)
	{
		if (a[g][j] == 1 || a[g][j] == 4 || a[g][j] == 9)
		{
			result = 1;
			break;
		}
		if (a[g][j] == 2) c2 = 1;
		else if (a[g][j] == 3) c3 = 1;
		else if (a[g][j] == 5) c5 = 1;
		else if (a[g][j] == 6) c6 = 1;
		else if (a[g][j] == 7) c7 = 1;
		if (c2 == 1 && c5 == 1)
		{
			result = 1;
			break;
		}
		if (c3 == 1 && c6 == 1)
		{
			result = 1;
			break;
		}
		if (c5 == 1 && c6 == 1 && c7 == 1)
		{
			result = 1;
			break;
		}
	}
	return result;
}

void dfs(int group, int num)//group代表第几组，num代表第几个数字
{
	if (group == 4)//此时已输完，递归结束
	{
		ans++;
		return;
	}

	for (int i = 1; i <= 9; i++)//从自然数1开始递归循环
	{
		if (b[i]!=1)
		{
			b[i] = 1;
			a[group][num] = i;
			if (num == g[group])//数字已填满，判断是否合法
			{
				if (vaild(group, num))
				{
					dfs(group + 1, 1);
				}
			}
			else//数字还未填满，去找下一个数字
			{
				dfs(group, num + 1);
			}
			b[i] = 0;
		}
	}
}

int main()
{
	scanf_s("%d %d %d", &g[1], &g[2], &g[3]);
	dfs(1, 1);
	printf_s("%d", ans);
	return 0;
}