查看: 1948|回复: 0

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

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 15:58 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
结果: 208-2=206
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[10][10];
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
int ans;

void output() {
for(int i = 1;i<= 6;i++) {
      for(int j = 1;j<= 6;j++) {
         cout<<vis[j]<<' ';. ?, f8 {& ]3 h# O9 n6 }3 D! n- m
      }
0 p2 t& ]2 F; L. E! B       cout<<endl;' C4 _2 Q  R+ C) X
}
2 [! w/ f0 E+ g" y% x3 K9 h cout<<endl<<endl;
: ~* f8 v0 ~$ d}
( C0 \8 z# }6 ~7 A; e, ~, \/ L4 A& G
0 c2 \* e  G) N2 D8 B) Xvoid dfs(int x,int y,int step) {
* Y  i) x$ t3 B if(step> 6) {/ M1 i' \; S, u% \5 }, x
      return ;
' _% @# N( c. L( {" y) } }3 [: ^% ^$ R% \* z5 N0 B1 ^; X
if(x == 1&&y == 1&&vis[1][1] == true) {4 |! _% w: D2 N$ v( ?* B0 W
      ans++;
; s8 D* n8 ^5 t9 E5 G6 p% T$ d       output();- p: e3 A5 f7 s  I' o' V& X
      return ;" ^/ z5 X) _1 x. b
}
3 V4 V" J, ?, z6 I for(int i = 0;i< 4;i++) {" J, p0 O( R9 i7 U: M
      int tx = x+ne[0];
9 U/ O) |. @4 A) i* \2 @9 {4 ?       int ty = y+ne[1];! }2 B8 |7 X$ d: h/ G# L# J- g

; l& Q- Q, u) k2 H7 L. a  ]       if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;5 R# p/ L3 _. z" S5 N
      vis[tx][ty] = true;# W) r: c( i. J, J) R% a
      dfs(tx,ty,step+1);
5 ]' I0 \% n+ N4 G) h       vis[tx][ty] = false;
3 |0 ~# r& b) O3 T2 P }
! G: T( b# `# o. Y return ;
9 C, ?  E6 ^8 F1 F, z}
+ K6 G3 T2 z5 q
1 q* G4 I( ^' Gint main() {. ^4 ~! }4 K! u% m  j% P
dfs(1,1,0);* ^* n$ i) K& @" l: Z6 `! H( A
cout<<ans<<endl;% s) ^* \5 ?$ v) T, h
  j" l# Q! V# _- C- {2 ^6 p' g$ C
return 0;; R, Q" q7 u* D  y5 |8 s1 }* z+ @# B
}
# t" P0 K; I" g' a, b5 m) R+ I---------------------
: x1 W) S) z8 a% F, w3 N. P2 F作者：nka_kun 8 ~! S- @/ w( D
来源：CSDN
' C5 W% m/ V0 x3 v. T" f
! |3 X9 y$ {0 z7 G
" b9 O; x: Y% ?0 e" M& V2 J