数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第五题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:58
标题:
2019第十届蓝桥杯B组决赛题解第五题
2019第十届蓝桥杯B组决赛题解第五题
9 n0 m( X( E0 {$ G6 _7 \
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
4 L, ^' t0 R3 Y* a2 A+ \1 |
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
& g0 w1 O. Q0 o: W7 S
结果: 208-2=206
! S, K# o* W% K9 Y5 W: O2 D" }. H* H
代码:
9 I u: c! O- \" Q n6 _& m
#include<bits/stdc++.h>
- m& R% f( b9 `; o: e
#define mem(a,b) memset(a,b,sizeof(a))
" `7 j' E$ m) [- z" z# Z
using namespace std;
8 |" Y" E! k. I6 `, Y! G3 B6 c
typedef long long ll;
# H8 z$ ~) W( U% m; N3 g
const int inf = 0x3f3f3f3f;
. {/ p& G3 R1 l6 w' H+ V" ^- u* B
const int maxn = 3e5+55555;
+ V# ~' @% j/ I8 e$ |" u
const ll mod = 998244353;
& j$ A" z+ H% ?
const double eps = 1e-7;
+ D! J% S' \3 H) X2 e9 Y
( }& i6 [: [" g( U, j9 `% B: [
bool vis[10][10];
: P# \" o5 ~& v% O
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
5 h; v) R9 b x, k i! I
int ans;
# f0 b/ }6 s0 q, K7 H! U, V
' `; a" D# C3 X: x* v
void output() {
. o9 {+ {/ L& @' }
for(int i = 1;i<= 6;i++) {
+ c+ w1 O% e4 W8 N1 \6 {* G1 g
for(int j = 1;j<= 6;j++) {
0 j, B, i$ G b( g8 s, I' s
cout<<vis
[j]<<' ';
, F5 U2 d. m0 @. i
}
6 m+ v" U, l% l) k3 Y, s* P% d
cout<<endl;
- l# J/ F- V6 q* v
}
2 f4 s9 n; t5 x/ f7 X2 C4 R1 ~3 k
cout<<endl<<endl;
7 ?5 u7 B) q$ \ O2 D1 i2 _1 H8 y
}
" o2 y0 u5 _1 e
# ], G7 r, }7 B
void dfs(int x,int y,int step) {
; L. e* c( ]2 `1 M/ y
if(step> 6) {
2 z" R1 j" u7 N5 X! T
return ;
9 ^6 u" ^4 @5 ?# S( g/ @
}
6 @ i& o# [! y, [! Y! n
if(x == 1&&y == 1&&vis[1][1] == true) {
$ w! f. S& p( ~% @1 f' Y0 r2 J
ans++;
) y: X; N2 s; b
output();
2 \. `6 x* c) M! e5 w
return ;
, L1 N' N" I' N8 `8 _
}
3 H* B. h6 S/ I8 C
for(int i = 0;i< 4;i++) {
l; A- o6 g3 q3 b* ]: g& x7 }# b
int tx = x+ne
[0];
1 i1 q9 N' |" I
int ty = y+ne
[1];
# Z4 N8 ], n& C2 { i. @' m" @
! l, m5 T Q6 T' |+ p3 t$ e( \( j
if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
: u s; t" e: j$ W7 F" e& R
vis[tx][ty] = true;
' Y6 R1 t0 D. o8 `8 m. E" Y& s% L2 S! K
dfs(tx,ty,step+1);
! M+ K9 R" H5 I* n# Q
vis[tx][ty] = false;
; l2 F. a, }$ @
}
m# a$ I D& C t" Q+ ]: c) u
return ;
5 m: \% ?) L( r8 E6 l: H9 ^
}
/ q& w. U7 b% p) G
0 O% [5 k5 X, X
int main() {
) o9 j3 D8 K* B' L* ^( P
dfs(1,1,0);
2 e6 H- z. [8 b
cout<<ans<<endl;
6 D# [! |0 R7 R) j
, j2 z+ ?/ Q O; I' N8 b
return 0;
3 v6 \- i# A! z
}
2 z# w1 K1 y- g
---------------------
1 W* g B# P( z \
作者：nka_kun
, f. h e, b; e9 M- D
来源：CSDN
; n0 i6 N* _+ D/ G4 S
* N- \( Q4 }$ _( u d, Y
( T5 }( L4 q9 h9 Z
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5