数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第五题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:58
标题:
2019第十届蓝桥杯B组决赛题解第五题
2019第十届蓝桥杯B组决赛题解第五题
% ~ h* P* A" ]1 l% q, H& f# j$ ^( R
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
' e9 \" y0 ?& ]9 T; e
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
2 `+ ? F% Y/ h* h% t! N- q
结果: 208-2=206
& w. [2 [. S Y5 ?; D# k; P; m
代码:
! Y! `6 @( O) U
#include<bits/stdc++.h>
. U& W, B: ?( B. F8 Z' N2 t
#define mem(a,b) memset(a,b,sizeof(a))
* d8 } V& b$ m" J
using namespace std;
: b6 ]( {% D7 ]) s
typedef long long ll;
# h0 k! H( Y( b2 N: S
const int inf = 0x3f3f3f3f;
2 q2 K" H; Q. R) S, h: o
const int maxn = 3e5+55555;
+ b. z& i$ x. m7 S7 j
const ll mod = 998244353;
0 X' m. t+ g. u$ j
const double eps = 1e-7;
3 m. [$ s. a9 h: D: J
5 l0 \- J# k/ q, R1 M
bool vis[10][10];
4 C, Y: N7 V/ N4 V- J
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
( A7 H$ }/ f: `% h+ S7 x$ J6 \, }
int ans;
9 v# v4 t9 T/ e |1 s
8 H/ ^. {# V' \7 w$ }4 U
void output() {
" O! c0 ]% H3 P8 ~" u5 f
for(int i = 1;i<= 6;i++) {
8 Q8 B3 Q, j8 }0 I" f! r0 s D9 \
for(int j = 1;j<= 6;j++) {
; t" x- V( r3 H6 Q k) ~# V
cout<<vis
[j]<<' ';
( k* B9 t: J' H: P% q
}
|, b8 y! d0 }" p
cout<<endl;
5 A& `8 K# f& M3 N+ r% \
}
3 C, i5 B( \/ E; e0 [( Z
cout<<endl<<endl;
+ _ ~0 @: P! N9 s; @4 F( Y
}
$ k" t2 V) a, l
$ b8 P2 y: [3 R2 ]$ \
void dfs(int x,int y,int step) {
a, p8 H, W: w0 V+ d' c% }" i
if(step> 6) {
7 D8 ~8 P( a& y3 n `5 f
return ;
* i' o! |9 Z; o+ Z
}
3 P) ]# t* ]5 s6 X% e
if(x == 1&&y == 1&&vis[1][1] == true) {
- ]6 E7 I; p" g8 P
ans++;
) r4 a) F0 A8 o
output();
1 X. R5 } L3 ~6 f7 \) q5 X; Z$ F7 Q
return ;
' ]7 s% V: c+ C. V
}
; D I) D! C+ T4 [6 h8 O2 N+ ^* P
for(int i = 0;i< 4;i++) {
1 s# Q4 o1 q& U7 D2 K
int tx = x+ne
[0];
6 C1 `: E5 {# b& `# o) a8 k
int ty = y+ne
[1];
* s/ U& R7 i6 S& ^9 I
8 Z' o$ x& Z1 }: v' c1 _
if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
u6 ^5 E6 d, U; \
vis[tx][ty] = true;
( p$ l. M- S4 Q
dfs(tx,ty,step+1);
" G! w) Y5 i. J
vis[tx][ty] = false;
) R6 A3 |8 p, c: F
}
L3 L; n1 `7 q3 |3 w3 r- y
return ;
/ n4 C# \# s3 ?* K4 ]; u
}
( d1 m) s7 l) i1 b
* v5 q1 Y6 E5 B) X# ]) Y# ~3 `7 H
int main() {
* ^7 L* L0 S' ^$ H/ K" ?7 A0 F r
dfs(1,1,0);
\# @9 G6 o: [: w: V( P
cout<<ans<<endl;
. t2 V9 Y7 ~, b" m. A) i# O
4 Y7 E4 N6 [: B5 U/ s
return 0;
- z/ ^ P8 z- c4 M+ d
}
/ ]. @. ~) g6 [9 u; B
---------------------
' g. Y0 u' L i7 p, f5 U
作者：nka_kun
1 _, x! I9 i) r# ^1 C3 l
来源：CSDN
$ y# K$ H( ?$ ?/ u! f: Y
; |2 ?4 D1 s8 C- x& d" d% {$ ]
) U3 z! p9 a. O
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5