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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
- |8 d4 H+ C1 _+ C直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
代码:
+ ?' o% a: B6 D: A0 M8 r# C! o#include<bits/stdc++.h>
$ A% I2 e8 k6 _, e/ S  s# Q#define mem(a,b) memset(a,b,sizeof(a))
& G8 c. I+ G5 N* D! Lusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
2 J- Y. l& a+ F0 Zconst int maxn = 3e5+55555;
! J9 W4 c( Q' }const ll mod = 998244353;
const double eps = 1e-7;

$ `& m' ~5 H; z% t7 s1 Wbool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
( V2 x1 K  F2 Xint ans;
7 l9 M4 x* z; ?# k/ J2 z% o
" Z' H1 T- r( A/ k& W$ n; C$ H- Evoid output() {
    for(int i = 1;i<= 6;i++) {
( a% G& c- D- T. m% u5 W        for(int j = 1;j<= 6;j++) {
: X5 q3 N+ o, l4 U; P* j. h            cout<<vis[j]<<' ';
( T! w7 D( \" {( `        }
+ G" y. m% t5 C1 F        cout<<endl;
0 F  H: s) r7 r4 I1 d    }
" Q2 `: X0 Z+ P: W% F, {% k    cout<<endl<<endl;
. G/ Z; P' o( I' o/ d% v' A}

void dfs(int x,int y,int step) {
    if(step> 6) {
! V+ P8 s0 a5 Q" z+ O- c) b+ ?        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
0 \: Y- L* l% B+ h        ans++;
4 s# H1 G$ e8 j$ E        output();
        return ;
    }
    for(int i = 0;i< 4;i++) {
; R/ o+ k5 U* E* {, c        int tx = x+ne[0];
        int ty = y+ne[1];

! k+ V2 q4 R$ W/ x7 _        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
; i7 C2 ?' l1 m: `. ~; ~0 ]3 Q        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
    }
. l2 G; i/ e9 k' r3 T8 g0 b    return ;
}
6 ]) X6 ^& h- q; Q/ q: a
9 ]9 _0 V9 O2 ^) rint main() {
    dfs(1,1,0);
6 s  {5 u& J! s9 J: c% a* j, G. p( `    cout<<ans<<endl;
1 G$ r0 l2 M# i2 w$ R$ R# i
( `- I; \; k% C2 ~5 Z: Y0 K# v  ^    return 0;
}
---------------------
% o; C1 T& s1 L2 L. V% ]3 g. _作者：nka_kun
2 n( i' ~! t8 P. e/ @( @来源：CSDN

) B7 [6 T- {) T- J' ?- ]( ?& x