比赛 20150421 评测结果 AATTTTTTTT
题目名称 走道铺砖问题 最终得分 20
用户昵称 清羽 运行时间 8.464 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2015-04-21 11:12:07
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=50;

char buf[40];
long long n,m,A[maxn][maxn];

template<class T> inline bool getd(T& x)
{
	int ch=getchar();
	bool neg=false;
	while(ch!=EOF && ch!='-' && !isdigit(ch)) ch=getchar();
	if(ch==EOF) return false;
	if(ch=='-'){
		neg=true;
		ch=getchar();
	}
	x=ch-'0';
	while(isdigit(ch=getchar())) x=x*10+ch-'0';
	if(neg) x=-x;
	return true;
}

template<class M> inline void putd(M x)
{
	int p=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x==0) buf[p++]=0;
	while(x){
		buf[p++]=x%10;
		x/=10;
	}
	for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
	putchar('\n');
}

bool in(int x,int y){
	return (x>=0 && y>=0 && x<n && y<m);
}


void print()
{
	printf("\n");
	for(int i=0;i<n;i++){
	    for(int j=0;j<m;j++) printf("%d",A[i][j]);
		printf("\n");
	}
}

long long dfs()
{
//	print();
	long long ans=0;
	bool over=true;
	for(int i=0;i<n;i++){
	    for(int j=0;j<m;j++){
			if(A[i][j]) continue;
			over=false;
			if(in(i+1,j) && A[i+1][j]==0){
				A[i][j]=A[i+1][j]=1;
				ans+=dfs();
				A[i][j]=A[i+1][j]=0;
			}
			if(in(i-1,j) && A[i-1][j]==0){
				A[i][j]=A[i-1][j]=1;
				ans+=dfs();
				A[i][j]=A[i-1][j]=0;
			}
			if(in(i,j+1) && A[i][j+1]==0){
				A[i][j]=A[i][j+1]=1;
				ans+=dfs();
				A[i][j]=A[i][j+1]=0;
			}
			if(in(i,j-1) && A[i][j-1]==0){
				A[i][j]=A[i][j-1]=1;
				ans+=dfs();
				A[i][j]=A[i][j-1]=0;
			}
			break;
	    }
	    if(!over) break;
	}
	if(over) return 1;
	return ans;
}

void init()
{
	memset(A,0,sizeof(A));
	getd(n);getd(m);
}

void work()
{
	putd(dfs());
}

int main()
{
	freopen("floor.in","r",stdin);
	freopen("floor.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}