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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
* t6 _& R5 |# ^' N$ @在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
3 o5 C$ J$ K5 |# K直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
  X  Q9 Y6 N4 ~0 E5 ~8 I代码:
#include<bits/stdc++.h>
% h- A7 k) C) `9 j% W' z#define mem(a,b) memset(a,b,sizeof(a))
' ]7 t# e4 G, ?4 [* vusing namespace std;
. }! e; i* e  t8 r, ~typedef long long ll;
& M: j* z' i: R2 v1 }: e1 x& Z2 [const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
3 \8 O4 l: B& S8 i5 `/ hconst ll mod = 998244353;
const double eps = 1e-7;

bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
- D% J$ _/ U6 q" oint ans;
5 R0 G; K" J0 q( C0 H
void output() {
    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
; y; `# a' I2 N- j: ~+ u  S. L            cout<<vis[j]<<' ';
% F2 m, p- _& B% O0 B        }
        cout<<endl;
! T$ w: \; v, o+ i* Q1 N    }
, Q- L# F8 @$ ?# l+ r' R8 s9 r    cout<<endl<<endl;
}
$ q& a9 |3 L" L3 j+ a
" G& A5 B7 ]. q# ?9 avoid dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
    }
0 y+ M3 s9 |% V- b, b; F    if(x == 1&&y == 1&&vis[1][1] == true) {
7 @$ A; W% T( R4 ]        ans++;
/ c1 j. k" o5 N' `0 n        output();
& g0 X/ R& n7 P% ^; `6 K        return ;
    }
/ A" h  |7 u7 s" j    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
- ~* B9 }, g- V; c/ x/ `4 W  Z% a- v        int ty = y+ne[1];

        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
" N4 D4 D7 f1 A# r        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
- N1 ?9 c: p& U: ~7 a! G        vis[tx][ty] = false;
( f8 w, l8 _7 B/ W9 w2 ?9 d+ f+ l    }
3 p6 Z+ v, o& |/ @; M1 V1 ]    return ;
}
. o' m9 j- \! j  A2 b; Y: Y
int main() {
9 m1 y- l; Q" u& _% b( g3 R    dfs(1,1,0);
! @* }! k- z3 p( K    cout<<ans<<endl;

, c5 \& K# F% ?* V1 n    return 0;
4 b4 G5 K+ e  D$ |, `0 \2 ?+ w}
---------------------
- c8 Z# D  J4 ~! c作者：nka_kun
来源：CSDN