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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
% e. V. V4 `8 r; f! [直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
- }1 X( l- ^3 E* d结果: 208-2=206   
/ F. s+ f5 V$ |0 @# B! Y* g1 u7 b代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
! O. T. z, G* |8 Z- @3 _4 ~using namespace std;
% h; o) t* k0 Wtypedef long long ll;
0 g8 T# ]2 ^2 i5 D0 V' W$ Sconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
  x" y0 C8 P8 S/ M0 P1 F( g! nconst ll mod = 998244353;
const double eps = 1e-7;
0 i8 G* |  b* P/ x; y
- w- W$ @1 R& Q3 ybool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;

  U" Z5 i3 h8 t* n8 u7 I( zvoid output() {
    for(int i = 1;i<= 6;i++) {
3 E0 I, L# q$ x. H8 {        for(int j = 1;j<= 6;j++) {
' S; T* Y6 k* X4 j4 N2 c            cout<<vis[j]<<' ';
+ O/ e' f: _3 o9 K- x0 H* U$ n        }
# h  Q8 r. u& \  Z0 `' P# U        cout<<endl;
* M) r5 F/ K- J1 X* Q: l    }
    cout<<endl<<endl;
! l; \2 p8 S" y6 d3 ^: t}
5 d) {1 Z3 s9 y+ A
void dfs(int x,int y,int step) {
' H+ c0 U9 V: y0 U' y2 O4 S) P    if(step> 6) {
2 Q# A# {  q  ^* C        return ;
' R8 g: Q; Z% B; @, x    }
  K3 g% d) r; s; m2 f    if(x == 1&&y == 1&&vis[1][1] == true) {
  e1 P2 S7 O" X) ]" e        ans++;
; d% C: F8 G! `6 |        output();
- u5 c( I, q# O: P7 o5 F' {        return ;
7 j1 e* A& D. D- x) z, t& S    }
4 B  ^5 d# y& o( {$ m; }4 F, R  M    for(int i = 0;i< 4;i++) {
5 [' S' b9 A, ~( f$ n9 D% }9 [        int tx = x+ne[0];
! i! m: ~5 Q$ r/ D0 h        int ty = y+ne[1];
/ ]. {, f- e/ A$ z* Y# E
        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
        vis[tx][ty] = true;
        dfs(tx,ty,step+1);
( Q+ [, S1 T8 U& `6 I        vis[tx][ty] = false;
4 |5 V$ @. ^6 f/ ^) _3 K    }
! Z, g7 ^' Q* L5 G' m! |; g6 R) E    return ;
" F% k8 b; q) j/ x5 O7 Y# O5 K}
0 }5 t" V/ |* W( z: c% J& W
int main() {
" R2 b; @0 a; V6 r* `  d    dfs(1,1,0);
# \( e8 \$ E. J- P+ j! U& J: d5 ?    cout<<ans<<endl;

    return 0;
9 F  h( Y' I- R6 R}
---------------------
作者：nka_kun
1 a, C% A. A# j7 d0 }( n& H来源：CSDN
: Q1 u& K* _& K0 V# M( E/ S, y
' q7 A: ]' m" B; v* N/ @