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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
% M  n5 c; M$ H, _; @在一个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>
+ y0 [9 w# Z. l+ H1 ?* i- S#define mem(a,b) memset(a,b,sizeof(a))
6 o5 g7 H5 E7 C0 r6 D, S" o8 G! \using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
1 [1 u; Q6 s3 B7 c; S) fconst ll mod = 998244353;
const double eps = 1e-7;
$ e% X' k& C$ N4 p8 P4 }9 k' y! Y; _( R
bool vis[10][10];
9 S3 ]3 H% ~. F4 y9 n3 Rint ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;
1 s3 ~2 v8 T; \& a' b
. x/ _. m9 _2 D. V  Y/ s! pvoid output() {
    for(int i = 1;i<= 6;i++) {
; _- G/ p- J7 s$ Z3 d        for(int j = 1;j<= 6;j++) {
& x8 O* i, y/ l6 O4 w) V            cout<<vis[j]<<' ';
        }
        cout<<endl;
8 J4 l9 a2 C$ I, c/ b2 E, Y- g    }
9 a* s3 z( I" {( l* Q8 B+ ^    cout<<endl<<endl;
}
0 R: X/ k1 E! B3 W
void dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
* B. w- m: y1 f. {" ]    }
+ K: P+ D( M6 d' S. C    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
9 `4 C1 |" m- h3 b3 l5 r$ L        output();
+ P9 Z: v3 C( o1 X        return ;
3 }: g1 O: {: a+ m# Y+ d    }
4 h  w% \1 C9 k, Q! z    for(int i = 0;i< 4;i++) {
        int tx = x+ne[0];
        int ty = y+ne[1];
# i0 V* r& ^7 n  F8 K5 A
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
/ D. g2 B3 j5 e! t* G2 X( g        vis[tx][ty] = true;
  n1 }* V, x2 ?        dfs(tx,ty,step+1);
1 P# a  Q1 ~) @& t        vis[tx][ty] = false;
    }
    return ;
}
4 z' c, Y- Z. m* H* d, r( x
int main() {
    dfs(1,1,0);
9 ~* k4 q, w4 \: j- j6 f4 y    cout<<ans<<endl;
9 j) k" ~# @6 \+ H% |9 \9 @
4 O2 m9 ^  v1 v4 z( Z6 k    return 0;
}
---------------------
作者：nka_kun
来源：CSDN


. A5 s' X) _& n4 A' v