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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
: k* T* Z+ f5 j在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
% Z6 L. b; [  v9 Y# U; @结果: 208-2=206   
代码:
) H  |. T* N1 r, l+ [" G) `#include<bits/stdc++.h>
8 ?) M5 E4 G. s6 J- z#define mem(a,b) memset(a,b,sizeof(a))
) Q" E9 F' G2 s% I2 ~  ]+ Busing namespace std;
typedef long long ll;
* h/ w2 M( p  v7 `9 q' f: H. yconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
3 S* C3 y0 \- b/ o( q% {9 Q. Wconst ll mod = 998244353;
7 z0 D$ c/ Q/ k) Tconst double eps = 1e-7;

bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;

, i& U, o1 J# ~: T  Q8 Gvoid output() {
; g0 L! ^! w( L8 V    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
            cout<<vis[j]<<' ';
3 ?5 D' J' \, q        }
        cout<<endl;
    }
    cout<<endl<<endl;
. y+ R7 N; Y% z+ l: d  j8 C}
( v& K/ X2 Q# N, c) B" T
void dfs(int x,int y,int step) {
: p5 {2 t  {# }& I& S* C! o    if(step> 6) {
7 y2 J, x4 K  J+ W& C        return ;
4 n/ A! W. H0 O) E0 E" R5 V% b    }
+ g) n# w$ @  e5 R: x* M    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
0 g1 J& E4 ]* v, S( L        return ;
    }
) p2 \, Z4 ?+ w/ e- b% A    for(int i = 0;i< 4;i++) {
. u% l# W) V/ |  K. R  A5 ^2 m        int tx = x+ne[0];
        int ty = y+ne[1];

        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
        vis[tx][ty] = true;
) T& \( {) S3 {/ R        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
    }
! _* {* _, [4 r$ s0 B    return ;
! T9 ~' o0 H/ Q, @}
, z% g7 r4 V% u) n
int main() {
( r1 o3 v6 C+ z2 p    dfs(1,1,0);
    cout<<ans<<endl;

5 N, @8 X7 o& |' N$ [! z" P    return 0;
}
---------------------
作者：nka_kun
8 e, c  }) Y. f, c, f( |来源：CSDN

) M$ }1 u6 j* v, b4 h: Z
! ^( h8 p" F- r( Q, _' z