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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
# G) ]9 x$ [5 C  c. G) T) ]在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
* O5 {0 n+ s, D- ?' t直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
0 J* {; z6 @% q; J结果: 208-2=206   
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
* W$ g) B, ]1 G5 K8 [1 susing namespace std;
typedef long long ll;
( A" }" |1 B& a, `% \! oconst int inf = 0x3f3f3f3f;
" c' `5 o2 @! D1 D2 ]2 q0 o! Nconst int maxn = 3e5+55555;
) g* f& r' T9 O  ^const ll mod = 998244353;
$ a0 ?  X+ V1 [- L# F. L+ J: pconst double eps = 1e-7;

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

void output() {
    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
0 C2 x( J' A% v3 j            cout<<vis[j]<<' ';
        }
        cout<<endl;
    }
    cout<<endl<<endl;
}
: @$ J; Z8 K: Z, U7 Q
. F  {! Y* j+ S9 `# qvoid dfs(int x,int y,int step) {
# E; @0 B1 A* V6 H    if(step> 6) {
        return ;
2 b9 O, Y* n4 b" A    }
1 U" v+ g4 g! |" E7 n+ f    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
1 i( B( E- i1 O* E; E        output();
7 z$ p* u7 ]$ \9 F' ~0 B. s        return ;
, c9 F- J4 U9 W    }
/ I( b$ c- L" L* `: p% p9 e& G    for(int i = 0;i< 4;i++) {
! w8 M5 |# E* g3 M/ w        int tx = x+ne[0];
( K& W. e$ ]% |; ?( N% G4 A        int ty = y+ne[1];
( J$ y) f* c8 B0 R6 A) t: D
* p* r* C8 w, l        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;
2 [. L0 `* C6 T6 X8 D+ i- v    }
    return ;
}
+ x1 @+ ~2 l. c
& w8 l" @9 R9 L- k$ v! eint main() {
    dfs(1,1,0);
    cout<<ans<<endl;

# A! `/ \& j$ M6 {4 p    return 0;
2 K0 _7 r/ s- a+ b! X}
---------------------
$ |" _$ N% k! d; l* n% Q) o作者：nka_kun
来源：CSDN