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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
1 z0 _" K- {" N4 L  i4 ?8 ^$ x/ L在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
! j1 U( \- M0 l3 F% Q- F" _, Cusing namespace std;
4 `% \% Y( ~; p( rtypedef long long ll;
const int inf = 0x3f3f3f3f;
1 m' [7 T* r# F. @) I+ Lconst int maxn = 3e5+55555;
const ll mod = 998244353;
1 [2 R/ H0 X4 C/ ~const double eps = 1e-7;
' S) b% w/ y7 ?9 m: o% {
bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;
5 Q+ o( ]8 f  G) M3 F6 z7 ]+ M
  L0 r$ N" w& g3 jvoid output() {
    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
8 U/ w: l  a5 r0 B2 _* _; O( N            cout<<vis[j]<<' ';
        }
        cout<<endl;
    }
    cout<<endl<<endl;
}
5 [3 f% K- R  B. c
void dfs(int x,int y,int step) {
# Y6 d! ?+ o) C( w( [" |, t    if(step> 6) {
+ n5 m  R6 f6 E9 l" ?$ E        return ;
: n5 B' r: i+ @/ N$ e* H0 ~5 @    }
( p! [6 [, l9 c+ P    if(x == 1&&y == 1&&vis[1][1] == true) {
/ |" t9 ~& [, E        ans++;
        output();
        return ;
( J+ g7 L. {1 P( \& W7 f" a    }
    for(int i = 0;i< 4;i++) {
) ^0 M6 j0 _. v! G* S9 ^' S        int tx = x+ne[0];
        int ty = y+ne[1];

4 x0 m# e7 Y  E8 X) y0 F1 X4 W        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
        vis[tx][ty] = true;
$ }0 X- Y2 h0 e. G3 L% ]3 T        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
8 _6 h4 a+ U6 e0 ]5 M    }
    return ;
}

int main() {
    dfs(1,1,0);
( I' C. \+ ~8 v2 u  D    cout<<ans<<endl;

    return 0;
9 |: s$ f4 P9 j8 H- E8 Y}
---------------------
作者：nka_kun
来源：CSDN
9 N! r) T5 t# c; m! i; K
* u6 h& F  p/ ]