P8642 题解

wukaichen888 · 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;
}