普通dfs+回溯只能7/10 …

C++ 代码

#include<iostream>
using namespace std;
int rem[41];  //剩余靶子
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; 
int n,flag;  //flag标记是否找到答案
int list[1000],vis[21][21];  //存储路径和记录已访问

void dfs(int x,int y,int step){
    if(flag)return;
    vis[x][y] = 1;
    list[step] = (x-1)*n + y-1;
    rem[y]--;
    rem[n+x]--;
    if(x==n && y==n){
        for(int i=1; i<=2*n; i++){
            if(rem[i]!=0)return;
        }
        flag = 1;
        for(int i=1; i<=step; i++)cout<<list[i]<<" ";
    }
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx>=1 && nx<=n && ny>=1 && ny<=n && !vis[nx][ny] && rem[ny]>0 && rem[n+nx]>0){
            dfs(nx, ny, step+1);
            vis[nx][ny] = 0;
            rem[ny]++;
            rem[n+nx]++;
        }
    }
}

int main(){
    cin>>n;
    for(int i=1; i<=2*n; i++)cin>>rem[i];
    dfs(1, 1, 1);
    return 0;
}