[藍橋杯 2016 國 AC] 路徑之謎
題目描述
小明冒充 X X X 星球的騎士，進入了一個奇怪的城堡。
城堡里邊什么都沒有，只有方形石頭鋪成的地面。
假設城堡地面是 n × n n\times n n×n 個方格。如圖所示。
按習俗，騎士要從西北角走到東南角。
可以橫向或縱向移動，但不能斜著走，也不能跳躍。
每走到一個新方格，就要向正北方和正西方各射一箭。
（城堡的西墻和北墻內各有 n n n 個靶子）
同一個方格只允許經過一次。但不必做完所有的方格。
如果只給出靶子上箭的數目，你能推斷出騎士的行走路線嗎？
有時是可以的，比如如圖中的例子。
本題的要求就是已知箭靶數字，求騎士的行走路徑（測試數據保證路徑唯一）
輸入格式
第一行一個整數 N ( 0 < N < 20 ) N(0<N<20) N(0<N<20)，表示地面有 N × N N \times N N×N 個方格。
第二行 N N N 個整數，空格分開，表示北邊的箭靶上的數字（自西向東）
第三行 N N N 個整數，空格分開，表示西邊的箭靶上的數字（自北向南）
輸出格式
一行若干個整數，表示騎士路徑。
為了方便表示，我們約定每個小格子用一個數字代表，從西北角開始編號 $:0,1,2,3 \cdots $。
比如，圖中的方塊編號為：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
樣例 #1
樣例輸入 #1
4
2 4 3 4
4 3 3 3
樣例輸出 #1
0 4 5 1 2 3 7 11 10 9 13 14 15
提示
時限 1 秒, 256M。藍橋杯 2016 年第七屆國賽
眾所周知，藍橋杯獎水題不水
經過兩個小時的折磨，終于做出來了，網上的題解能不能先把題目過了再發。。
使用dfs，運用減枝，開四個數組來標記，然后就是dfs常規的了，但是題目各種細節，使人心力交瘁
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int g[N][N];
bool vis[N][N];
int path[450];
int n,cnt,k;
bool f;
int ax[N],ay[N];
int bx[N],by[N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool check()
{for(int i=1;i<=n;i++){if(bx[i]!=ax[i]||by[i]!=ay[i])return 0;}return 1;
}void dfs(int x,int y)
{if(f) return ;if(x==n&&y==n&&check()){for(int i=0;i<cnt;i++)cout<<path[i]<<" ";f=1;return;}for(int i=0;i<4;i++){int xxx=x+dx[i],yyy=y+dy[i];if(vis[xxx][yyy]||xxx<1||xxx>n||yyy<1||yyy>n||bx[xxx]>=ax[xxx]||by[yyy]>=ay[yyy])continue;bx[xxx] ++;by[yyy] ++;vis[xxx][yyy]=true;path[cnt++]=g[xxx][yyy];dfs(xxx,yyy);bx[xxx] --;by[yyy] --;vis[xxx][yyy]=false;path[cnt--]=-1; }}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>ay[i];for(int i=1;i<=n;i++)cin>>ax[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=k++;}}vis[1][1]=true;path[0]=0;cout<<"0"<<" ";bx[1]=1,by[1]=1;dfs(1,1);return 0;
}
)
)
