数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第五题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:58
标题:
2019第十届蓝桥杯B组决赛题解第五题
2019第十届蓝桥杯B组决赛题解第五题
* e0 e& Y$ G( {' g# B/ s
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
5 V: E0 D. n [/ a& [. w
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
# V" X8 P& j, z5 `5 a8 `
结果: 208-2=206
9 u% K6 n& Z& f8 K
代码:
; E4 x9 W$ I H" x0 o2 G/ g' N
#include<bits/stdc++.h>
- e Y7 j# U: [/ q1 o# N
#define mem(a,b) memset(a,b,sizeof(a))
+ w9 J! k5 \& @* N% V
using namespace std;
* ~# k8 _4 j# ^- _4 _4 g3 A0 U: e
typedef long long ll;
* H" g3 I5 X0 j7 ~1 L; J
const int inf = 0x3f3f3f3f;
& a2 `8 l/ M& v6 g
const int maxn = 3e5+55555;
# j* s7 a' k a# i5 u$ }' d! {# u3 n
const ll mod = 998244353;
4 ^! x7 F8 L4 L. z' r
const double eps = 1e-7;
( g1 S a& g ^
! p8 I4 H1 Z, \9 D
bool vis[10][10];
# s" k) Y; D1 v% r" }* g
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
- e& M/ S5 j: P) }
int ans;
4 d s' i! q5 K' m
5 d" X7 L+ w- S% Y5 H
void output() {
0 n9 Z3 r: O% Z9 d8 F$ k9 m
for(int i = 1;i<= 6;i++) {
0 z# c! a9 ]& [
for(int j = 1;j<= 6;j++) {
0 X! G1 H6 Y( |5 ^+ f! Z4 ~8 d3 R
cout<<vis
[j]<<' ';
2 C$ `' ^. T/ @
}
2 P1 D+ _: U1 e% b
cout<<endl;
; Z3 M0 u7 d" n! Q8 h0 F( m
}
) C# W7 v5 U" s
cout<<endl<<endl;
6 k( s1 K& {1 F' G, ]# k
}
2 Y& ^6 X- a6 n, T* Y
8 |) |6 j( }' }3 v
void dfs(int x,int y,int step) {
2 `" `9 ~/ j1 D h: ^
if(step> 6) {
3 L0 a$ y! X0 F, f& L: n
return ;
2 x1 W$ B/ S8 A. m" U
}
0 m8 R" A$ D8 M( p+ T5 J
if(x == 1&&y == 1&&vis[1][1] == true) {
3 c% z! w/ E* U- M I8 v
ans++;
8 [; {, O: b ~; R8 {* R
output();
! T- o7 [$ \4 s4 c% B
return ;
; L+ c. o9 [3 O1 N
}
! m/ Y4 z& L( }' C
for(int i = 0;i< 4;i++) {
4 u+ [' T# ` y. p% A8 w& J
int tx = x+ne
[0];
. H' L# I. x+ q" p; W
int ty = y+ne
[1];
# n$ N0 b+ ^) |0 \4 S
- w- Z6 M" {2 ^% J$ E
if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
0 k/ J0 |" P1 B c" L
vis[tx][ty] = true;
% x. P) B& h+ T$ B, H
dfs(tx,ty,step+1);
% i: Q( J# k7 L* `1 ?
vis[tx][ty] = false;
: |- T3 N6 Q' Y" `- v
}
3 j" ^! ]9 P2 l/ X$ Y
return ;
' K, }1 `1 p- B; p( @/ ^8 z
}
$ ~! m8 W4 M0 W# t
6 Q5 V! s! D+ y. r! q. z
int main() {
8 t0 v9 ~/ D/ z* f s
dfs(1,1,0);
7 k/ u5 }/ [) @" x
cout<<ans<<endl;
1 y- F! ^" Z2 R8 \) B- G
/ U, y, F3 M3 \2 d5 v9 F
return 0;
. F; o" |$ u3 O, L& G6 N. ~5 T
}
9 m+ R2 v9 P" b7 F0 n
---------------------
# b3 I# D8 Q, U0 C" m
作者：nka_kun
2 ? x' b# C+ \5 g& T, L
来源：CSDN
# e8 W0 ~& V8 x6 v" \1 Q
" t5 J U& }! S0 ^& @# a% |2 T
9 Y3 C) m% B& M& M1 s! d
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5