不开o2 TLE一个,该如何优化
查看原帖
不开o2 TLE一个,该如何优化
1122916
BLACK11楼主2024/5/29 00:35
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define ft first
#define sd second 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
const int INF=0x3f3f3f3f;
const int MN=1e5+20;
int ans[500];
bool vis[25][25];
pii mv[4]={{0,1},{0,-1},{1,0},{-1,0}};
int hen[30],zon[30];
int rec_h[30],rec_z[30];
int n;
bool flag=false;
void dfs(int x,int y,int cen){
	if(flag==true) return;
	ans[cen]=(x-1)*n+y-1;
	if(x==n && y==n){
		for(int i=1;i<=n;i++) if(rec_h[i]!=hen[i]) return;
		for(int i=1;i<=n;i++) if(rec_z[i]!=zon[i]) return;
		flag=true;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+mv[i].ft,ny=y+mv[i].sd;
		if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==false && rec_h[ny]+1<=hen[ny] && rec_z[nx]<=zon[nx]){
			vis[nx][ny]=true;
			rec_h[ny]++,rec_z[nx]++;
			dfs(nx,ny,cen+1);
			vis[nx][ny]=false;
			rec_h[ny]--,rec_z[nx]--;
		}
	}
	
	return;
}
void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> hen[i];
	for(int i=1;i<=n;i++) cin >> zon[i];
	vis[1][1]=true;
	rec_h[1]++,rec_z[1]++;
	dfs(1,1,1);
	for(int i=1;i<=n*n;i++){
		cout << ans[i] << ' ';
		if(ans[i]==n*n-1) break;
	}
	cout << '\n';
	//for(int i=1;i<=n;i++) cout << hen[i] << ' ';
	//cout << '\n';
	//for(int i=1;i<=n;i++) cout << rec_h[i] << ' ';
	return; 
}

int main(){
	FAST;
//	int _;
//	cin >> _;
//	while(_--)
	solve();
	return 0;
} 
2024/5/29 00:35
加载中...