洛谷P1380，pts70

常规
1

题目

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],xa,ya,n,m,t;
void dfs(int x,int y,int s)
{
	t=max(t,s);
	if(x==n&&y==m) return;
	if(y==m) xa=x+1,ya=1;
	else ya=y+1;
	if(x+2<=n&&y+2<=m&&!a[x][y]&&!a[x][y+1]&&!a[x+1][y+1]&&!a[x][y+2]&&!a[x+2][y+1])
	{
		a[x][y]=1;
		a[x][y+1]=1;
		a[x+1][y+1]=1;
		a[x][y+2]=1;
		a[x+2][y+1]=1;
		dfs(xa,ya,s+1);
		a[x][y]=0;
		a[x][y+1]=0;
		a[x+1][y+1]=0;
		a[x][y+2]=0;
		a[x+2][y+1]=0;
	}
	if(x+2<=n&&y+2<=m&&!a[x+1][y]&&!a[x][y+2]&&!a[x+1][y+1]&&!a[x+1][y+2]&&!a[x+2][y+2])
	{
		a[x+1][y]=1;
		a[x][y+2]=1;
		a[x+1][y+1]=1;
		a[x+1][y+2]=1;
		a[x+2][y+2]=1;
		dfs(xa,ya,s+1);
		a[x+1][y]=0;
		a[x][y+2]=0;
		a[x+1][y+1]=0;
		a[x+1][y+2]=0;
		a[x+2][y+2]=0;
	}
	if(x+2<=n&&y+2<=m&&!a[x][y+1]&&!a[x+1][y+1]&&!a[x+2][y]&&!a[x+2][y+1]&&!a[x+2][y+2])
	{
		a[x][y+1]=1;
		a[x+1][y+1]=1;
		a[x+2][y]=1;
		a[x+2][y+1]=1;
		a[x+2][y+2]=1;
		dfs(xa,ya,s+1);
		a[x][y+1]=0;
		a[x+1][y+1]=0;
		a[x+2][y]=0;
		a[x+2][y+1]=0;
		a[x+2][y+2]=0;
	}
	if(x+2<=n&&y+2<=m&&!a[x][y]&&!a[x+1][y]&&!a[x+2][y]&&!a[x+1][y+1]&&!a[x+1][y+2])
	{
		a[x][y]=1;
		a[x+1][y]=1;
		a[x+2][y]=1;
		a[x+1][y+1]=1;
		a[x+1][y+2]=1;
		dfs(xa,ya,s+1);
		a[x][y]=0;
		a[x+1][y]=0;
		a[x+2][y]=0;
		a[x+1][y+1]=0;
		a[x+1][y+2]=0;
	}
	dfs(xa,ya,s);
}
int main()
{
	cin>>n>>m;
	dfs(1,1,0);
	cout<<t;
	return 0;
}
2 个赞
3

能说说我哪里错了吗

3 个赞
4

改成了50分

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],b[1001][1001],xa,ya,n,m,t;
void dfs(int x,int y,int s)
{
	if(x==n)
	{
		t=max(t,s);
		return;
	}
	if(y==m-1) xa=x+1,ya=2;
	else xa=x,ya=y+1;
	if(s+1>=b[x][y])
	{
		b[x][y]=max(b[x][y],s);
		if(!a[x][y]&&!a[x-1][y-1]&&!a[x-1][y]&&!a[x-1][y+1]&&!a[x+1][y])
		{
			a[x][y]=1;
			a[x-1][y-1]=1;
			a[x-1][y]=1;
			a[x-1][y+1]=1;
			a[x+1][y]=1;
			dfs(xa,ya,s+1);
			a[x][y]=0;
			a[x-1][y-1]=0;
			a[x-1][y]=0;
			a[x-1][y+1]=0;
			a[x+1][y]=0;
		}
		if(!a[x][y]&&!a[x][y-1]&&!a[x][y+1]&&!a[x-1][y+1]&&!a[x+1][y+1])
		{
			a[x][y]=1;
			a[x][y-1]=1;
			a[x][y+1]=1;
			a[x-1][y+1]=1;
			a[x+1][y+1]=1;
			dfs(xa,ya,s+1);
			a[x][y]=0;
			a[x][y-1]=0;
			a[x][y+1]=0;
			a[x-1][y+1]=0;
			a[x+1][y+1]=0;
		}
		if(!a[x][y]&&!a[x-1][y]&&!a[x+1][y-1]&&!a[x+1][y]&&!a[x+1][y+1])
		{
			a[x][y]=1;
			a[x-1][y]=1;
			a[x+1][y-1]=1;
			a[x+1][y]=1;
			a[x+1][y+1]=1;
			dfs(xa,ya,s+1);
			a[x][y]=0;
			a[x-1][y]=0;
			a[x+1][y-1]=0;
			a[x+1][y]=0;
			a[x+1][y+1]=0;
		}
		if(!a[x][y]&&!a[x-1][y-1]&&!a[x][y-1]&&!a[x][y+1]&&!a[x+1][y-1])
		{
			a[x][y]=1;
			a[x-1][y-1]=1;
			a[x][y-1]=1;
			a[x][y+1]=1;
			a[x+1][y-1]=1;
			dfs(xa,ya,s+1);
			a[x][y]=0;
			a[x-1][y-1]=0;
			a[x][y-1]=0;
			a[x][y+1]=0;
			a[x+1][y-1]=0;
		}	
	}
	dfs(xa,ya,s);
}
int main()
{
	cin>>n>>m;
	if(n<3||m<3)
	{
		cout<<0;
		return 0;
	}
	dfs(2,2,0);
	cout<<t;
	return 0;
}
2 个赞
5

改了一下过了

2 个赞
6

%%%%%%%%%%%%%%%%%%%%%%%\color{white}。