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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
" ]- u. G5 l4 R4 {+ n& l' b4 h' a在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
* V# J* ?# E' }$ G6 S6 U, p4 ^直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
+ _6 H5 c; z6 m' i8 ~% v( o1 N结果: 208-2=206   
代码:
! D  _$ }- v  b5 i#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
" T; @$ Z; X& z4 b& Eusing namespace std;
8 \" |, \9 z; Htypedef long long ll;
const int inf = 0x3f3f3f3f;
3 j/ g. p- q) q4 `& \0 _) D0 d' aconst int maxn = 3e5+55555;
const ll mod = 998244353;
7 t" K# G7 M+ t! n4 uconst double eps = 1e-7;

bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
. k) U0 N7 @: t& a7 h5 w4 fint ans;

5 _- Q) s$ v2 r, S; a2 Z) {3 ]void output() {
    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
- u& e6 {5 m( y+ ?  A' H8 A( f0 E            cout<<vis[j]<<' ';
        }
        cout<<endl;
, R- _4 p, \# }2 i: M8 l1 A2 r    }
    cout<<endl<<endl;
; ~: n7 ~) [  v}

8 U' O5 O/ i5 u2 Q" E1 e& N( pvoid dfs(int x,int y,int step) {
0 v+ O2 i; r# t+ p' U! b/ F7 ^    if(step> 6) {
        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
! p% U# f) m. o        return ;
    }
/ E9 b: f; F0 t$ s5 O0 c6 G/ K    for(int i = 0;i< 4;i++) {
$ X9 c- p' I/ w! y: l/ j        int tx = x+ne[0];
        int ty = y+ne[1];

        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
2 }* S6 q6 C& h5 P0 n& i. Q1 q% s        vis[tx][ty] = true;
& T2 ?4 P- a. S8 C7 h" {        dfs(tx,ty,step+1);
4 x9 r5 P4 z8 t, B1 \        vis[tx][ty] = false;
1 K- C9 u  f# N% j) v" k0 X3 G, v    }
+ Q; e5 p& G) O  D    return ;
}
1 d4 ]. H) V: m
int main() {
    dfs(1,1,0);
    cout<<ans<<endl;

: z% ], u/ o" S$ H3 u/ c7 U    return 0;
}
( o& L+ W* O- b: `2 _. k. P7 U---------------------
作者：nka_kun
来源：CSDN
' ^3 `0 O9 K! n: m