只会dfs搜了个70分代码

截至2021.4.6 本题无人AC
期待大神AC，教教我咋写QAQ

C++ 代码（70分）

#include <bits/stdc++.h>
using namespace std;
const int N=25;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int n,north[N],west[N],now_n[N],now_w[N];
bool flag=0,vis[N][N];
struct node
{
    int x,y;
};
vector<node>path;
bool judge(int now_n[],int now_w[])
{
    for(int i=1;i<=n;i++)
        if(now_n[i]!=north[i]||now_w[i]!=west[i])
            return 0;
    return 1;
}
void dfs(int x,int y,int now_n[],int now_w[],vector<node>path)
{
    if(flag)return;
    if(x==n&&y==n&&judge(now_n,now_w))
    {
        if(!flag)
        {
            flag=1;
            for(int i=0;i<path.size();i++)
                printf("%d ",(path[i].x-1)*n+path[i].y-1);
            printf("\n");
        }
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx<1||nx>n||ny<1||ny>n||now_n[ny]+1>north[ny]||now_w[nx]+1>west[nx]||vis[nx][ny])continue;
        // change
        path.push_back({nx,ny}),now_n[ny]++,now_w[nx]++,vis[nx][ny]=1;
        // get into deeper level and continue searching
        dfs(nx,ny,now_n,now_w,path);
        // trace back
        path.pop_back(),now_n[ny]--,now_w[nx]--,vis[nx][ny]=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>north[i];
    for(int i=1;i<=n;i++)
        cin>>west[i];
    now_n[1]=1;
    now_w[1]=1;
    path.push_back({1,1});
    dfs(1,1,now_n,now_w,path);
    return 0;
}
/*
10
9 4 1 1 9 8 7 8 7 9
7 8 7 6 7 4 7 7 4 6
ans:
0 10 11 21 31 30 40 50 60 70 80 90 91 92 93 94 84 85 75 74 64 65 55 45 44 34 24 14 4 5 15 25 26 16 6 7 17 18 8 9 19 29 28 27 37 38 39 49 48 47 46 56 57 67 66 76 77 78 68 69 79 89 99
*/

附赠数据：

input

19

13 16 13 12 12 11 10 12 11 11 13 12 3 3 4 1 2 3 1
6 5 8 7 5 9 10 8 6 7 10 8 13 9 13 10 10 11 8

output

0 19 38 39 20 1 2 3 22 23 4 5 24 43 44 45 64 65 84 103 122 141 140 121 102 101 82 81 100 99 118 117 136 155 154 135 116 115 96 97 98 79 60 61 42 41 40 59 58 57 76 95 114 133 152 153 172 173 174 175 194 195 196 197 198 199 180 181 162 143 142 123 124 125 144 163 182 201 200 219 220 239 238 237 218 217 236 255 274 273 254 235 216 215 234 253 252 233 232 231 230 211 192 191 210 229 248 267 266 285 304 323 324 305 286 287 268 269 270 289 308 309 328 347 348 329 310 311 330 331 332 351 352 353 354 335 334 333 314 315 296 295 294 275 256 257 276 277 278 279 260 241 242 261 280 299 300 301 320 321 340 359 360