如果用dfs超时怎么办啊orz
查看原帖
如果用dfs超时怎么办啊orz
1091683
sheenaringo楼主2023/11/1 21:01
using namespace std;
int n,m,x2,y2,a[30][30];
long long sum=0;
int dx[9]={1,2,2,1,-1,-2,-2,-1,0},dy[9]={2,1,-1,-2,-2,-1,1,2,0};
void dfs(int x,int y){
	if(x==n&&y==m){
		sum++;
		return;
	}
	if(x>n||y>m){
		return;
	}
	if(a[x+1][y]!=1){
	a[x+1][y]=1;
	dfs(x+1,y);
	a[x+1][y]=0;
	}
	if(a[x][y+1]!=1){
		a[x][y+1]=1;
		dfs(x,y+1);
		a[x][y+1]=0;
	
	}
}

int main(){
	scanf("%d%d%d%d",&n,&m,&x2,&y2);
	n+=2;m+=2;x2+=2;y2+=2;
	memset(a,0,sizeof(a));
	for(int i=0;i<9;i++){
		a[x2+dx[i]][y2+dy[i]]=1;
	}
	dfs(2,2);
	cout<<sum;
	return 0;
}
2023/11/1 21:01
加载中...