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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
( L/ u1 Q6 o+ ]5 Q( p5 j. a在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
  c# T" o+ ]5 v" ]) u代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
: V* C3 `9 j8 T/ H+ R1 ~const int maxn = 3e5+55555;
const ll mod = 998244353;
6 T3 C+ Q0 @( x' k' P1 L( nconst double eps = 1e-7;

, l8 ?, j- ?9 f& n8 T+ u! g0 k! mbool vis[10][10];
  K- m! A  ^2 ~( u$ d8 lint ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;
! j% g4 ^2 B, w6 s
, ]; r: U3 _/ s! O& L) x; Hvoid output() {
5 V& v3 s, f" H    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
            cout<<vis[j]<<' ';
        }
1 J7 @% g1 b. f" L; E' R! \        cout<<endl;
    }
5 \5 g2 I. H3 s. c) h5 \8 q5 H    cout<<endl<<endl;
! {" M$ a* h$ N  p% N1 c}

5 [. W; b# U/ x! M; F; Dvoid dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
    }
* x) W) v+ z" s    if(x == 1&&y == 1&&vis[1][1] == true) {
/ A8 w. T; {0 k1 x2 R" H0 q6 }9 o        ans++;
* L, p& W3 N3 t6 O9 n/ {$ S        output();
( N# C2 o: [7 ]8 ^  R1 y        return ;
$ [1 ~! P- S$ P2 M    }
    for(int i = 0;i< 4;i++) {
& P0 m: |$ a# a/ J' E6 i% m# V        int tx = x+ne[0];
        int ty = y+ne[1];

7 f6 C; W7 d# Q+ `        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
! b# n; F& {5 B8 Z$ `        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
' O; Z$ R: K6 d7 v0 d    }
    return ;
}
5 U  z7 q" P; E( W2 Z9 |
6 @5 ?6 h5 w- A2 ]' k: i) `int main() {
    dfs(1,1,0);
2 n2 G$ V5 l# f    cout<<ans<<endl;
* y% p0 ]; c. Q6 o* G! n
1 w+ ^. |2 S3 B6 b    return 0;
}
+ t  v% W' Z, F---------------------
作者：nka_kun
, O. p' [& F: l, [来源：CSDN

$ E: N( z* ^  y+ J* M& L* I
3 ], J- t; k5 Y- d