求大佬看看为什么我的运行时间总超时
查看原帖
求大佬看看为什么我的运行时间总超时
1266839
Yusiao楼主2024/4/5 14:10
#include<bits/stdc++.h>
using namespace std;

int N,l=0;
int state[20][20];
int trace[400];
int n1[20],n2[20];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool isover(){
	for(int k=0;k<N;k++){
		if(n1[k]!=0||n2[k]!=0){
			return false;
		}
	}
	return true;
}

void dfs(int i,int j){
	n1[i]--;
	n2[j]--;
	state[i][j]=1;
	trace[l]=i*N+j;
	if(i==N-1&&j==N-1){
		if(isover()){
			for(int k=0;k<l+1;k++){
				cout<<trace[k]<<" ";
			}
		exit(0);
		return;	
		}
	}
	for(int k=0;k<4;k++){
		if(i+dx[k]>=0&&i+dx[k]<N&&j+dy[k]>=0&&j+dy[k]<N){
			if((n1[i+dx[k]]>0||n2[j+dy[k]]>0)&&state[i+dx[k]][j+dy[k]]==0){
				l++;
				dfs(i+dx[k],j+dy[k]);
			}
		}
	}
	trace[l]=0;
	n1[i]++;
	n2[j]++;
	state[i][j]=0;
	l--;
	return;
}

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>n2[i];
	}
	for(int i=0;i<N;i++){
		cin>>n1[i];
	}
	memset(state,0,sizeof(state));
	dfs(0,0);
    return 0;
}
2024/4/5 14:10
加载中...