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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
' n+ a6 p: A' w! E7 L' L9 w7 G3 ]直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
9 n( M1 D& i9 B' G/ P5 f0 ~4 i代码:
* W1 W) q7 g% ~0 X1 l. R, H% ^#include<bits/stdc++.h>
6 L  d+ U: l* U! D5 d; B/ F/ Q7 o#define mem(a,b) memset(a,b,sizeof(a))
& i: m/ K; ^3 f; H/ K; Qusing namespace std;
( @$ P5 Z- q+ b* q! J# {typedef long long ll;
- E6 ~0 t5 J) a$ V7 bconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
/ f) u" L  f7 u# T- k  w! bconst double eps = 1e-7;

bool vis[10][10];
6 D4 o2 ?7 P7 a6 Vint ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;
1 ~8 C; _  }% I# V. v1 R4 X
) n+ S& \3 p  N7 L* s( Svoid output() {
    for(int i = 1;i<= 6;i++) {
$ @9 ~$ g4 {  H# Y! h. P        for(int j = 1;j<= 6;j++) {
5 A: A, K9 L1 a1 K* k7 a            cout<<vis[j]<<' ';
        }
# O# }9 T+ \7 |        cout<<endl;
    }
; y1 a0 \% e, I' C. J* b( c' Q    cout<<endl<<endl;
}

! W6 y3 f$ W5 I6 ovoid dfs(int x,int y,int step) {
    if(step> 6) {
+ z( x5 h# U+ }$ t        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
5 t7 R  D3 t+ ?5 D        ans++;
1 C: g. X8 ~1 n# w2 V        output();
& P" C0 T8 k; N  f        return ;
    }
; {6 P: n" p6 ^. I8 j    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
' B4 Z8 h6 p* T' j; G" S3 ]        int ty = y+ne[1];

        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
6 F7 H& E% }4 P: D2 Q2 L" p/ S# V        vis[tx][ty] = true;
9 X# R0 [8 _7 c$ W  O        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
5 l: M6 I2 Q9 Z4 T' l3 x    }
9 Z# I) L# C* m  E    return ;
4 R6 z  T% J: G7 F1 d% S% K}

int main() {
1 Q. ^; i3 [3 x' m. s& V    dfs(1,1,0);
, ?/ o7 b' y' Z8 K- ~) j: M4 T9 R    cout<<ans<<endl;

9 J* Z9 G$ C, k8 I3 }    return 0;
}
---------------------
  v  U3 q- e  C# o4 A作者：nka_kun
7 {, B- N# |% E9 H; M来源：CSDN


/ K. ?5 H% O, j3 F4 s