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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
. k( n3 B% y1 \在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206   
& W6 L, Q. Z+ d6 u) N* d+ S, m代码:
#include<bits/stdc++.h>
; `+ j/ v5 T% l; O1 ?#define mem(a,b) memset(a,b,sizeof(a))
" X+ u- U* S! E# f: Cusing namespace std;
& Z7 d/ R+ j& q. {2 \- vtypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

  {# N5 p3 F; D: O% b; p+ d$ \bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
. X0 V) {1 o  iint ans;

void output() {
    for(int i = 1;i<= 6;i++) {
/ j9 w$ n, j1 E6 D9 l" K: Z1 J        for(int j = 1;j<= 6;j++) {
+ w5 f; z( O' @4 _; ]9 }& E& c            cout<<vis[j]<<' ';
8 ^. D, i6 c: g1 d6 |# ~/ q        }
        cout<<endl;
: u. \! q* f4 E; T    }
    cout<<endl<<endl;
}

( T, e3 ~, N/ _# [/ f5 h; z6 bvoid dfs(int x,int y,int step) {
    if(step> 6) {
        return ;
    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
        output();
7 W. W% X5 j4 @  E        return ;
/ P* x# ~+ y6 D: O    }
. \3 Y6 M; c0 J/ g( W    for(int i = 0;i< 4;i++) {
0 |5 f7 g% s% N1 v( F* c        int tx = x+ne[0];
& y, F: I: R7 q- X# Z, V        int ty = y+ne[1];
  M! L! _# q8 S
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
        vis[tx][ty] = false;
    }
& q0 R  f7 L( Y) E, ?    return ;
# d- A1 n' m! F5 O}
' p4 D  Y7 G# n9 P
int main() {
    dfs(1,1,0);
    cout<<ans<<endl;

% J5 B3 d) S. u# i    return 0;
& I- u# o1 A3 Y) |1 ~  g}
---------------------
# ^/ z. p& H/ f7 u3 N' w$ {作者：nka_kun
来源：CSDN

7 E2 H' h7 m2 m1 {
$ D( N: @, j' e* ]