求调,只过了一个,写了注释
查看原帖
求调,只过了一个,写了注释
1138579
Lazy_Durant楼主2024/4/19 11:37
#include<iostream>
using namespace std;

const int N = 30;
int xx[N], yy[N], dx[5], dy[5], n, re;
bool vis[N][N];
struct node{
    int x, y;
}res[N], ans[N];

void dfs(int x, int y, int num){
    if(x == n && y == n){
        int flag = 0;
        //如果走到了,但是靶子上还有箭,即不都为0,就不记录该条路径 
        for(int i = 1; i <= n; i++){
            if(xx[i]) flag = 1;
            if(yy[i]) flag = 1;
        }
        if(!flag){
            for(int i = 1; i <= num; i++) ans[i] = res[i];
            re = num-1;
        }
        return ;
    }
    for(int i = 1; i <= 4; i++){
        int x1 = x + dx[i];
        int y1 = y + dy[i];
        //检查是否走过,是否越界 ,靶子上有没有箭,没 
        if(vis[x1][y1] || x1 < 1 || y1 < 1 || x1 > n || y1 > n || xx[x1] < 1 || yy[y1] < 1) continue;
        xx[x1]--, yy[y1]--;
        vis[x1][y1] = true;
        res[num].x = x1, res[num].y = y1;
        dfs(x1, y1, num + 1);
        xx[x1]++, yy[y1]++;
        vis[x1][y1] = false;
    }
}

int main(){
	//xx数组存储竖着的靶子数量 
    //yy数组存储横着的靶子数量 
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", &yy[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &xx[i]);
    //dx,dy数组代表四个方向 
    dx[1] = -1, dx[2] = 1, dx[3] = 0, dx[4] = 0;
    dy[1] = 0, dy[2] = 0, dy[3] = -1, dy[4] = 1;
    //因为1,1点必走,我们对这个点上的靶子数量--; 
    xx[1]--, yy[1]--;
    dfs(1, 1, 2);
    for(int i = 1; i <= re; i++){
        // 将坐标转换为编号输出
        int num = (ans[i].x - 1) * n + (ans[i].y - 1);
        num=max(0,num);
        cout << num << " ";
    }
    return 0;
}

2024/4/19 11:37
加载中...