2019第十届蓝桥杯B组决赛题解第五题

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
. b6 i# N; g2 e: W1 ~直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
; L0 L6 T6 z0 c, ~代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
; o  }/ c5 T& E% Tconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
9 q9 u" J0 Q: tint ans;

/ |- Z5 ~. \& ]0 i6 ]9 Uvoid output() {
% u# ~: J. N, ~/ q9 T) ?; F5 L    for(int i = 1;i<= 6;i++) {
/ a- d- [( M8 l+ \* A  \        for(int j = 1;j<= 6;j++) {
            cout<<vis[j]<<' ';
9 A1 E1 }2 R$ }" t        }
        cout<<endl;
1 y/ y0 |7 v6 n; b* A9 I& S/ F; [+ M    }
    cout<<endl<<endl;
}
5 S' K% c' n: L! ^8 X2 c+ N. H
+ k: Q+ c0 H" q4 O% y  c9 B" x0 Evoid dfs(int x,int y,int step) {
0 l0 Y! [" ]( ^- u; K6 a    if(step> 6) {
; l2 j9 ?, z. H4 h+ v% ~0 o  Y        return ;
    }
/ Z- r5 A5 e) v& z) o/ O$ a    if(x == 1&&y == 1&&vis[1][1] == true) {
6 d5 ]& Y; i1 E7 X% A% l" E9 Z        ans++;
        output();
        return ;
4 B+ }5 G" A9 d+ Q. w6 H0 ~  c* @    }
    for(int i = 0;i< 4;i++) {
& d5 l' U5 r9 P2 r' p+ I' ~: i        int tx = x+ne[0];
" R7 q7 B. q; w6 }% e6 }        int ty = y+ne[1];
1 J' O) R. E9 j! u: k  U
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
5 a! u4 e, e+ `& E9 N        vis[tx][ty] = true;
9 \4 s  h& {/ O        dfs(tx,ty,step+1);
1 d4 M! r4 Z3 U6 ?+ n* C5 [% k        vis[tx][ty] = false;
- |: s/ O7 ^# s5 p1 S    }
    return ;
) Y6 I2 s; ?6 u, `( O/ g% T}
# n9 Q! O* q3 G- }  Y$ V
0 ^! c* o& E9 X& v  f" cint main() {
    dfs(1,1,0);
9 D2 U' P  H: d# z    cout<<ans<<endl;

    return 0;
}
---------------------
作者：nka_kun
9 ]/ Y6 \1 X2 o) \6 @/ N来源：CSDN

' d: v8 D, s7 W7 V3 \* U( p