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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
7 W! x  X( x* K7 \) d在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
8 _. J1 y- F! V0 u% `- m7 ^直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
9 O& m( D+ ?& t2 G结果: 208-2=206   
; u/ Y- G: C! x0 m代码:
$ x8 ^# X  a, c; R: D( F8 x#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
% H1 B+ `# ~+ E  Y7 Qconst int maxn = 3e5+55555;
7 l' V+ w+ l2 w  y6 K  @const ll mod = 998244353;
const double eps = 1e-7;
* r: W" g2 L# F7 N
bool vis[10][10];
( j' [6 a1 f! ?# Y; j7 Gint ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;

void output() {
  J+ B1 `  l- U/ k    for(int i = 1;i<= 6;i++) {
8 W2 k4 M! G/ G+ p* X! h        for(int j = 1;j<= 6;j++) {
9 K+ q6 r, l, I$ ]            cout<<vis[j]<<' ';
4 I& |/ a, N1 f1 A        }
        cout<<endl;
    }
7 O2 S4 O1 {4 U# v8 D" o) {  B    cout<<endl<<endl;
" z  I. W9 l! w}

void dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
6 w, t5 x! n; l3 z- ^; J    }
) t8 F2 u, K! ^+ b    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
1 S2 c' U" }% v( Z5 n1 m; T        return ;
    }
* p. p5 F" x$ d" n8 W9 W    for(int i = 0;i< 4;i++) {
1 P" d6 g( }1 ^- N" E2 p        int tx = x+ne[0];
- |6 [! D5 G/ K) J2 w4 X        int ty = y+ne[1];

" h! a7 ^( a2 R/ L. C9 J6 t        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
1 q9 i' |& o1 q2 j4 r        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
* I$ w0 o! ^7 L        vis[tx][ty] = false;
! `; f7 [/ J" Z6 ~1 C: d, X    }
1 i: h+ A7 B# S7 _    return ;
6 d$ M' B. T0 S  R6 P; p/ c}
5 A5 M  A3 i# |" O9 [* b# l
int main() {
3 W8 T2 `# J8 q- G, e1 g! F, H    dfs(1,1,0);
    cout<<ans<<endl;
- `+ a0 W$ |3 K4 j0 t
    return 0;
}
---------------------
作者：nka_kun
来源：CSDN
, v7 _+ y. D* q% z( ]- H8 ^
8 R# G' h( k* A; G
" f, k; w- W1 U6 P