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

杨利霞

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
, u& u% j2 h1 |直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
, C! j4 {/ y* n% y# M结果: 208-2=206   
7 `  I. l7 r( X5 |: n1 E2 m代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
5 Q8 G9 _/ F  J; r# u- dconst int inf = 0x3f3f3f3f;
, S) x+ w+ W1 J3 f: G- Wconst int maxn = 3e5+55555;
. l, U1 [6 ]% z+ G0 Kconst ll mod = 998244353;
1 g: l. W  Z! k0 D8 P6 I/ aconst double eps = 1e-7;
0 _! c- J/ `  [; Q1 G+ a2 S3 ~4 p; m7 |
bool vis[10][10];
" u& ~6 E% {  ?9 Rint ne[4][2] = {1,0,-1,0,0,1,0,-1};
) Y8 h7 L& o/ }4 `int ans;

, F! t% i$ T: k* J: i! _, bvoid output() {
( u% a0 n9 ~0 ?7 ^  M    for(int i = 1;i<= 6;i++) {
        for(int j = 1;j<= 6;j++) {
) z+ N  [0 U7 S$ @5 e" R! F( d% E% b            cout<<vis[j]<<' ';
7 N  g- c' w% F7 Y- P, g4 t; W1 I: h0 Z        }
+ Y& q7 |8 ^. A# Y        cout<<endl;
9 a7 m+ W' g8 {1 V    }
    cout<<endl<<endl;
3 K' m# H8 B6 v}

void dfs(int x,int y,int step) {
8 }$ S, S5 w* T# N! y    if(step> 6) {
        return ;
) r3 q! s; w, b) @( w    }
    if(x == 1&&y == 1&&vis[1][1] == true) {
        ans++;
) K) F. I6 B0 g2 h9 }# M        output();
( H- x) `2 X4 s( l. |# o+ ?        return ;
/ {2 D8 g/ M  F    }
    for(int i = 0;i< 4;i++) {
/ B- W/ a9 C3 E3 `        int tx = x+ne[0];
5 c( {1 T2 H/ `9 h1 F        int ty = y+ne[1];

" y# o; h# Z3 p6 S5 I        if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
2 S+ V+ J8 `' h7 ]/ [8 d! N! F8 ~        vis[tx][ty] = true;
8 n: D3 z3 b* l0 y; M        dfs(tx,ty,step+1);
4 V6 O) u  v4 @; H5 o/ m        vis[tx][ty] = false;
# V6 B+ V& e% n6 }    }
    return ;
}
9 T: l, ?1 f3 D4 s/ e+ b
, v4 S0 K6 H+ @4 X! O2 @$ Oint main() {
    dfs(1,1,0);
, y6 Q6 ^% C3 W! C. Z% @( Q- g    cout<<ans<<endl;
; u; A% |' E- W5 n; k
    return 0;
! J# p2 B/ N9 K, c}
2 A# w* {  u7 g3 u$ g$ c---------------------
作者：nka_kun
来源：CSDN


2 J# A* M8 O1 G9 N- ]