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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
) z( \6 }5 M' e! `8 U: K在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
! u* L2 K, K. R0 B+ }代码:
#include<bits/stdc++.h>
, L5 h- [' |' @# M7 s. t. b* X#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
$ ^2 x: @# C# Ltypedef long long ll;
const int inf = 0x3f3f3f3f;
5 x. r3 ]% u# V& A- G) e5 Jconst int maxn = 3e5+55555;
# k$ L9 W  L! E4 u5 ?+ w; m" `const ll mod = 998244353;
. W4 l6 }- ?4 Y, zconst double eps = 1e-7;

bool vis[10][10];
" H( \' w8 b* M3 H0 l, xint ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;

void output() {
( C2 R, ?6 Z+ g- ]* ?4 g* A% c    for(int i = 1;i<= 6;i++) {
6 M- _- z' F; J6 p2 J# O        for(int j = 1;j<= 6;j++) {
( w0 ]; [( M- {& ]% _, n! T3 |            cout<<vis[j]<<' ';
        }
        cout<<endl;
    }
! x, Z- N6 G" F, D& o/ ]2 s& [9 T3 m    cout<<endl<<endl;
* i# X9 {5 C+ ~}
1 |! m% G  R- W
# v" j6 A2 Z. {" xvoid dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
" l* R, ~- k, u& b    }
1 P! a% m) D  N* P) e! }6 _$ f/ v% }    if(x == 1&&y == 1&&vis[1][1] == true) {
, @7 r+ V3 {- U; t        ans++;
6 i5 l" {: q( @+ W        output();
        return ;
    }
    for(int i = 0;i< 4;i++) {
) W; z& N' t, _" G$ c; e3 `        int tx = x+ne[0];
        int ty = y+ne[1];
  w% m$ ~* T, g4 S$ g1 i
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
9 P/ V" P4 W( v2 M; ~        vis[tx][ty] = true;
, v1 x# K/ u  j% R0 ^( m; ~        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
    }
+ B- V3 W6 ^3 r: z' D    return ;
7 z% Y2 {4 r" `! b, m2 G. y* Q2 N}

& L+ x5 D6 b( jint main() {
    dfs(1,1,0);
    cout<<ans<<endl;

0 b2 F$ k2 q5 Q! i9 i    return 0;
}
" p+ g/ M8 @" E% B2 p---------------------
作者：nka_kun
来源：CSDN
) P; m3 A* q  _1 D$ Z' K