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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
% b* i" p/ f2 V- l: {5 C. Q在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
$ L! H% B8 ^. _/ G/ C! y5 V结果: 208-2=206   
( C. `7 Y" |5 s/ D) W5 B代码:
* G) P# C% e) S0 V' S/ T- J3 ^#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
0 d  k. }9 y! b5 P- pusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
* ?8 ^6 x! {1 @$ J  h, Tconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

9 ?2 ?0 T. A2 Q: a7 P$ |9 r* A* ibool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;
# V$ r  c4 G( E* |* J
void output() {
; d- R/ M& p& a/ F% ?  ?    for(int i = 1;i<= 6;i++) {
7 m: ^1 s  Y8 ^7 @2 G) P6 P        for(int j = 1;j<= 6;j++) {
            cout<<vis[j]<<' ';
        }
        cout<<endl;
6 m5 C6 |1 m# u1 d# R2 A    }
0 g5 z8 v  v$ r    cout<<endl<<endl;
}
* k8 W* C5 _5 V
void dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
        return ;
: w- B: k; P) l. C7 {    }
: D& A5 O; C! t+ z+ C7 N- t4 m! e    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
. }( G4 n$ m& @) f* c' _        int ty = y+ne[1];
. t1 D( b' n9 i5 a2 D9 [5 [- M
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
4 T' [( v) j% R4 \4 [- r        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
, Q, q/ o& a" r7 h; x        vis[tx][ty] = false;
% m" h- o8 k% Z0 v3 l3 u    }
. X* r0 c6 ~" D: V  N6 w+ h    return ;
}
: Y5 d' T& S' j5 S
5 o6 P5 x1 K9 |( ~int main() {
    dfs(1,1,0);
) I% N0 W! a9 b    cout<<ans<<endl;

1 i& S: T  K0 H9 Q! N5 Y! e    return 0;
}
---------------------
作者：nka_kun
1 T% F. g; k  n, q来源：CSDN
' I9 l- y& u6 v. D: f