自动搬运

查看原文

来自洛谷，原作者为

	wukaichen888 复健 OI

搬运于2025-08-24 22:41:00，当前版本为作者最后更新于2025-06-04 15:18:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

能够通过目前所有 hack 数据。

直接爆搜。

剪枝：假如当前无法到达终点，返回。

假如对行或列，当前位置不能往回折经过最靠上或左的位置，返回。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=25;
int n;
int cnt0[N],cnt1[N],sum,flag;
int vis[N][N],stk[N*N],top;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
inline int yyz(int x,int y){return (x-1)*n+(y-1);}
inline void ins(int x,int y){stk[++top]=yyz(x,y);}
inline bool check(int x,int y){return (cnt0[x]>=1)&&(cnt1[y]>=1)&&(!vis[x][y]);}
inline bool qwq(int x,int y){
	bool flag;
	flag=1;for(int i=x;i>=1;i--){if((!flag)&&cnt0[i])return 1;if(cnt0[i]<=(i!=x))flag=0;}
	flag=1;for(int i=y;i>=1;i--){if((!flag)&&cnt1[i])return 1;if(cnt1[i]<=(i!=y))flag=0;}
	for(int i=x+1;i<=n;i++)if(!cnt0[i])return 1;
	for(int i=y+1;i<=n;i++)if(!cnt1[i])return 1;
	return 0;
}
inline void dfs(int step,int x,int y){
	if((x==n)&&(y==n)){
		if(step==sum) ins(x,y),flag=1;
		return ;
	}
	if(qwq(x,y)) return ;
	vis[x][y]=1;
	for(int op=0,nx,ny;op<4;op++){
		nx=x+dx[op],ny=y+dy[op];
		if(check(nx,ny)){
			cnt0[nx]--,cnt1[ny]--;
			dfs(step+1,nx,ny);
			if(flag){ins(x,y);return ;}
			cnt0[nx]++,cnt1[ny]++;
		}
	}
	vis[x][y]=0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&cnt1[i]),sum+=cnt1[i];
	for(int i=1;i<=n;i++) scanf("%d",&cnt0[i]);
	cnt0[1]--,cnt1[1]--;
	dfs(1,1,1);
	while(top) printf("%d ",stk[top--]);
	return 0;
}