托米航空公司

NC16407. 托米航空公司

描述

托米老师靠才华与颜值发家致富后，开了一家航空公司，公司的口号是“您想飞，我们便做您的翅膀~让您每次飞行都有独特的体验！”

但是现在有一个小小的问题需要解决，托米家的飞机每排有M个座位，有N排座位。因此座椅形成了M × N的网格（忽略过道）,公司为每次航班都出售K张票。
为了满足口号中的“翅膀”部分，座位必须遵守以下规则：座位被占用时，座位正前方和座位后方的座位以及当前座位左边和右边必须是空的(大概是因为这个飞机会很大吧，boss就是这么任性哼)。
然后为了满足口号中的“独特体验”部分。公司则是对每一趟航班飞机的座位采取不同的安排，如果这一趟的某个座位是占用的，而另一趟的座位是空的，则这两趟飞机座位安排是不同的。
给你三个数字M，N和K。
现在需要从这些座位中选出k个合法的座位。由于这个数字可能非常大，我们只求它对420047取模的结果。

输入描述

输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由包含三个整数M，N和K的一行组成。

输出描述

对于每个测试用例输出一行，表示答案对420047取模的结果。

示例1

输入:

输出:

8
2
10

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 476K, 提交时间: 2019-07-10 15:29:14

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=420047; 
int bk[100][100];int n,m,k;
ll ans=0;
void dfs(int pos,int cnt){
	if(cnt==k){
		ans++;
		return;
	}
	if(pos==n*m+1)	return;
	int x=(pos-1)/m+1,y=(pos-1)%m+1;

	if(!bk[x-1][y]&&!bk[x+1][y]&&!bk[x][y-1]&&!bk[x][y+1])
	{
		bk[x][y]=1;
		dfs(pos+1,cnt+1);
	}
	bk[x][y]=0;
	dfs(pos+1,cnt);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		ans=0;
		scanf("%d%d%d",&n,&m,&k);
		memset(bk,0,sizeof(bk));
		dfs(1,0);
		printf("%lld\n",ans%mod);
	}
}

C++ 解法, 执行用时: 27ms, 内存消耗: 288K, 提交时间: 2021-11-16 15:58:51

#include<bits/stdc++.h>
using namespace std;
bool a[100][100];
long long sum=0,m,n,k;
void dg(int k,int t)
{
	int x,y;
	if(k==0)
	{
		sum++;
		return;
	}
	for(int i=t+1;i<=m*n;i++)
	{
		x=(i-1)%m+1;
		y=(i-x)/m+1;
		if(a[y-1][x]==0&&a[y][x-1]==0)
		{
			a[y][x]=1;
			dg(k-1,i);
			a[y][x]=0;
		}
	}
}
int main()
{
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		sum=0;
		memset(a,0,sizeof(a));
		cin>>m>>n>>k;
	 	dg(k,0);
	 	sum%=420047;
	 	cout<<sum<<endl;
	 } 
	return 0;
 }