数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第五题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:58
标题:
2019第十届蓝桥杯B组决赛题解第五题
2019第十届蓝桥杯B组决赛题解第五题
, Z1 Q$ @2 O5 v" V
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
" P- Z# L' \, _; D; c
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
" J. \/ P I& r8 x
结果: 208-2=206
, @! o! u. D9 @6 X; i& }
代码:
6 S7 i; d' Z5 v/ `: I2 E/ x
#include<bits/stdc++.h>
( p. e0 g# Z. d8 E# G
#define mem(a,b) memset(a,b,sizeof(a))
- X# |' k0 c v4 t* e1 [1 J' }5 l
using namespace std;
5 i7 L! W) |+ A- H
typedef long long ll;
# X! t# d5 k2 b+ H; |; S
const int inf = 0x3f3f3f3f;
+ r* w' w/ T6 h
const int maxn = 3e5+55555;
U6 f( Q9 M7 @+ ?8 K9 J* Y6 ?
const ll mod = 998244353;
X4 [: Y: D9 V4 x# H! [
const double eps = 1e-7;
8 y* u @: I6 x) ^7 w
1 @% C5 c1 C0 G% c5 c+ L2 C
bool vis[10][10];
; p' c% Z8 B* _
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
* H/ D! U5 {- J7 N
int ans;
* E5 @3 @7 s! C4 M) q
1 c, r& ~( d- `. |
void output() {
0 m$ R3 ^% P& o% r4 n1 K1 H
for(int i = 1;i<= 6;i++) {
. o& j% z1 n8 m- I+ X
for(int j = 1;j<= 6;j++) {
, ^3 d8 T+ n7 g, z
cout<<vis
[j]<<' ';
6 q7 o; ?% _0 \; b3 u: ^, P$ @
}
, q/ ?& d7 b! v7 p" O9 {
cout<<endl;
/ s' M) r4 i- k" S; _$ D
}
5 R( u U0 L) `( i
cout<<endl<<endl;
' y- X! K* p/ \
}
. m2 o7 h; `7 N3 t( ]$ n% {1 D
5 D: W4 Z9 s2 D% J, ~4 e
void dfs(int x,int y,int step) {
8 A3 [1 O; \) P4 P8 F
if(step> 6) {
- v1 U" H, [6 c Q$ m. T
return ;
) [8 K3 t6 w( P/ [6 H- O
}
% T0 N$ l2 ~8 I# u( z
if(x == 1&&y == 1&&vis[1][1] == true) {
* H0 C" p/ j# n: v
ans++;
1 @5 M! ?2 }' w. o
output();
* `0 d/ n) f4 F: e2 }
return ;
# k6 c4 t* N9 H: ?- V
}
8 m' `+ _% p6 `* k3 B, e1 g4 |' L
for(int i = 0;i< 4;i++) {
9 T. v1 G' @+ Z1 \/ M( ]8 L+ \
int tx = x+ne
[0];
8 K3 C/ ?- ^) j U
int ty = y+ne
[1];
5 L, ?, y6 A, v% x$ ?" l
, Q0 l1 G) Q* }9 X2 R# x
if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
" u1 Q, `) V$ D8 W/ I- ^
vis[tx][ty] = true;
3 a7 J: P; j( v5 d# N
dfs(tx,ty,step+1);
7 `/ l4 F2 F- g+ V, D
vis[tx][ty] = false;
9 ?) n6 }% y$ D- }
}
( h! |! Q+ k; \" Y1 n" R* ^
return ;
8 f4 m! i; S! r x% a( S8 T
}
3 [# j% \& }, n8 ^; ]% B; F+ E% T
$ ~6 {: U8 b* ^' m
int main() {
8 X: ]9 f/ i/ `
dfs(1,1,0);
k$ x; q7 o. Y) \! C. v" M) @( R: y
cout<<ans<<endl;
, O0 W' @* w: p3 T% |
; [+ {1 ]6 C' t% ?
return 0;
- C: E2 b9 d/ r t9 z* j
}
# M: Y8 |2 p; |% N
---------------------
, Q2 v) c. e' ?/ E
作者：nka_kun
) d2 X5 | n' F, u" M! N8 T8 T
来源：CSDN
- v7 I% R8 ^5 i! c" F
1 \0 W0 V2 Z( i% T% M
7 f+ e* p8 |; i3 `
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5