为什么P1002使用深搜会导致数据点3、4超时?
查看原帖
为什么P1002使用深搜会导致数据点3、4超时?
1118893
Dark_Star楼主2023/9/29 09:56
#include<bits/stdc++.h>
using namespace std;
bool f[22][22];long long sum;int n,m,x,y;
int mx[9]={0,2,1,-1,-2,-2,-1,1,2},cx[3]={0,1,0};
int my[9]={0,1,2,2,1,-1,-2,-2,-1},cy[3]={0,0,1};
void dfs(int x,int y)
{
	if(x==n&&y==m){sum++;return;}
	for(int i=1;i<=2;i++)
		if(f[x+cx[i]][y+cy[i]])dfs(x+cx[i],y+cy[i]);
}
int main()
{
	cin>>n>>m>>x>>y;
	for(int i=0;i<=21;i++)
		for(int j=0;j<=21;j++)
			if(i>n||j>m)f[i][j]=false;
			else f[i][j]=true;
	for(int i=0;i<=8;i++)
		if(x+mx[i]>=0&&x+mx[i]<=n)
			if(y+my[i]>=0&&y+my[i]<=m)
				f[x+mx[i]][y+my[i]]=false;
	dfs(0,0);
	cout<<sum;
	return 0;
}
2023/9/29 09:56
加载中...