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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
- g0 w, p8 I, ~7 `代码:
' H4 w6 ?1 v7 X. E( ]0 N#include<bits/stdc++.h>
" W# H' V* c( D+ K  c#define mem(a,b) memset(a,b,sizeof(a))
+ K/ O+ K- X1 susing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
' Z: T  f% P" J: f9 V0 |/ Xconst int maxn = 3e5+55555;
/ z+ Q) w5 A+ Uconst ll mod = 998244353;
const double eps = 1e-7;
2 U0 X. X0 K2 t( v# b& n' l
bool vis[10][10];
. W# [: O9 m, C/ pint ne[4][2] = {1,0,-1,0,0,1,0,-1};
# J' p( c' S0 Z6 B) h# y/ Mint ans;
6 ~6 j, m  U. X/ q7 Y/ [. M
/ o; k; A& [& s( Zvoid output() {
" f; e' g/ Q9 i: u, ~    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
            cout<<vis[j]<<' ';
        }
        cout<<endl;
3 I' I* @7 i1 `  C/ C* {6 j    }
    cout<<endl<<endl;
}

0 B% W/ L+ E+ G6 q! d/ k) q* tvoid dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
0 F: Z- s2 N3 l, _        ans++;
        output();
        return ;
    }
& h& O$ H7 N$ V9 D    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
        int ty = y+ne[1];
, S# x! C7 Z4 v; q# M! e
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
8 s- \7 ?- i" }: B% k' c% w- }    }
8 D8 g7 M( D$ V, j: I) Y    return ;
}
  G6 c5 A2 }1 K1 ?0 c
1 T+ k2 Q/ }1 k8 \int main() {
3 D9 K/ X( Q1 a    dfs(1,1,0);
0 c$ ^4 K! `2 ~" e1 t- J    cout<<ans<<endl;

- {- r" b; h+ i3 D" z/ z5 U3 [    return 0;
}
---------------------
, K4 \$ u' m. _/ g" `. g作者：nka_kun
. a, b7 q  P/ r, M  {. p来源：CSDN

7 s  G0 e8 W( S, d, z* h/ B
- ^) L2 W% P, D" I