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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
6 `2 E! b1 X6 A% {在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
2 c/ w) H6 B' f5 c$ e2 w直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
* R! F3 X9 z1 b4 y结果: 208-2=206   
代码:
; W0 [% n# {6 o3 }- z9 @#include<bits/stdc++.h>
) D- P' A& E( o( D1 Q1 ~#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
6 Q  P- d9 m: m( a+ Utypedef long long ll;
9 o8 w3 A# r9 I, x, x, Kconst int inf = 0x3f3f3f3f;
0 @8 Q: p  \/ ]8 P' ^5 \; ]# S3 u* ^const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
9 @6 z, ~% Z+ o5 K
bool vis[10][10];
( c* L, S) r% Z! \6 F# Vint ne[4][2] = {1,0,-1,0,0,1,0,-1};
; M1 W4 I6 t9 O% S/ D, Yint ans;

void output() {
- z- ^7 p1 |2 l3 _    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
, a) |  q9 T  S- |- m0 v# t            cout<<vis[j]<<' ';
        }
2 Y7 Z0 _0 v% {2 `  P! {* I# V+ v        cout<<endl;
' c# t3 [6 X$ X7 S' g7 N5 u" y+ U    }
    cout<<endl<<endl;
}
# L3 A/ o3 ^/ U! v
4 J/ _" J) ^* T! x$ zvoid dfs(int x,int y,int step) {
8 ~0 j& D2 t' y7 b' H    if(step> 6) {
        return ;
1 Q* p1 U# T1 L) m    }
- a. E) N8 w( a5 i    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
) z# |1 ]1 T0 d+ Q, ]" {# U        return ;
' t" r( Z, E7 M+ g    }
$ ]1 z2 d# S: e1 i    for(int i = 0;i< 4;i++) {
( u$ l  H2 ~2 {5 I6 [9 F% Z' R        int tx = x+ne[0];
& j* c$ t% N8 I- P' b" N3 {        int ty = y+ne[1];
( e- V5 e: i' I6 j9 m9 i
3 _" t* k9 A' r  b7 r        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
( L" M" ^$ |) I6 D& ~        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
( [8 o( l! F7 x        vis[tx][ty] = false;
% j" [; y4 l& K3 S/ m4 s' k$ |) i9 N    }
% u' u# G: H) t/ h, o    return ;
}
5 K; A4 ~" N/ a
# B* M8 p( J0 t4 y/ gint main() {
    dfs(1,1,0);
    cout<<ans<<endl;
5 }( A1 ]0 {1 e" m; b$ P
    return 0;
}
: A% w5 f( ]- Z. c; F* D---------------------
$ s4 x9 t6 e% j/ j作者：nka_kun
来源：CSDN
2 Z8 C3 z& D# R

. R% w; y+ p7 a+ D2 D( x+ _