试题 算法训练 车的放置

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)

输入格式

　　包含一个正整数n

输出格式

　　一个整数，表示放置车的方法数

样例输入

2

样例输出

7

数据规模和约定

　　n<=8
　　【样例解释】一个车都不放为1种，放置一个车有4种，放置2个车有2种。

思路：

        先给一个三维数组车c[10][10][10],c[i][j][k]=m就表示i行j列的矩阵放k个车有m种。

        接下来我们一行一行看一个矩阵，比如一个4*4的矩阵放3个车，是不是可以看成去掉一行一列，在剩下的三行三列中放2个车，因为第一行有4个元素，所以也就是c[3][3][2]*4，当到第二行时因为第一行的元素已经用过了，所以就相当于在剩下的两行三列放2个，也就是车c[2][3][2]*4,到了第三行已经用掉了两行，所以也就是车c[1][3][2]*4,但是一行三列不能放2个车。

        所以c[4][4][3]=c[3][3][2]*4+c[2][3][2]*4;

        同理就能的出规律：

        c[i][j][k]=j*c[i-1][j-1][k-1]+i*c[i-2][j-1][k-1]+j*c[i-3][j-1][k-1]+.....j*c[i-1-m][j-1][k-1](if(k>i-m)break)

运行结果：

代码：

//c[i][j][1]=i*j
//c[i][j][k]=j*c[i-1][j-1][k-1]+i*c[i-2][j-1][k-1]+j*c[i-3][j-1][k-1]+.....j*c[i-1-m][j-1][k-1](if(k>i-m)break)
#include
using namespace std;
int a[10][10] = { 0 };
int n;
int ans = 0;
int c[10][10][10] = { 0 };//c[i][j][k]=m,i*j的棋盘放k个车有m种
void init()
{
	memset(a, 0, sizeof(a));
}
int main()
{
	int m = 0;
	cin >> n;
	c[1][1][1] = 1;
	c[1][2][1] = 2;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <=n; j++)
		{
			for (int k = 0; k <= n; k++)
			{
				if (k == 0)
				{
					c[i][j][k] = 1;
				}
				else if (k == 1)
				{
					c[i][j][k] = i * j;
				}
				else
				{
					if (k > i - m)
					{
						break;
					}
					else
					{
						while (k <= i - m)
						{
							c[i][j][k] += c[i - 1 - m][j - 1][k - 1] * j;
							m++;
						}
					}
				}
				m = 0;
			}
		}
	}
	for (int i = 0; i <= n; i++)
	{
		ans += c[n][n][i];
	}
	cout << ans;
	return 0;
}