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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
; K, \$ a: e# v; A' h0 }: ^; E  ]9 w" _在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
6 u# t6 Y& R1 ^6 j$ s结果: 208-2=206   
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
3 g2 y* Z3 [# P. s- u8 fusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
2 X0 e4 r5 i7 _0 C1 O1 gconst int maxn = 3e5+55555;
2 {1 z+ P: A# [* ?6 Tconst ll mod = 998244353;
const double eps = 1e-7;
6 I& K* z- O: J& V: e: L
bool vis[10][10];
. z8 x* z/ v( Y4 tint ne[4][2] = {1,0,-1,0,0,1,0,-1};
7 |$ _& j1 R) {9 J+ r6 q- b7 Cint ans;
8 e  T5 k2 i' s* r8 ]
8 P5 S, t. b$ _, T- o* xvoid output() {
    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
' n+ g& \4 a, D2 x7 c1 Y$ M! v7 @  w            cout<<vis[j]<<' ';
2 n# M. C# O0 E: |  z8 E        }
        cout<<endl;
    }
* S+ |8 {4 g, k- d1 |9 N, I    cout<<endl<<endl;
}
7 m3 `# R/ K; q; f6 [4 o  d& J
void dfs(int x,int y,int step) {
    if(step> 6) {
3 f4 O6 W! C2 H6 Z# R        return ;
" @  I% Q5 p1 Y    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
4 f% k" |' G4 Y/ ]- u" ~2 f        return ;
2 q) R& i) i0 l  e( ]    }
    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
: J9 Q+ k; P+ t# X. ]1 X/ d. g        int ty = y+ne[1];
/ j3 U# A# r/ K4 R, W) V8 ~7 Z7 p
! Z1 V7 y+ @$ `( [0 ?8 ~: T        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
' ]" _2 C4 j! Z4 i        vis[tx][ty] = true;
) k5 a: `6 Y6 P. |( m2 N        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
2 M. E& P9 B/ d! }. a2 h5 \3 J6 w    }
6 I. y7 z' t1 R8 k    return ;
}
6 e1 O1 f( @: x, l5 i2 ^! {# L$ B
+ O9 }0 d: N, nint main() {
    dfs(1,1,0);
    cout<<ans<<endl;
# k, c( f0 O, g
    return 0;
}
, z9 R) W' F" ~---------------------
作者：nka_kun
来源：CSDN


; I. v5 ?- P5 G