查看: 1849|回复: 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]<<' ';
! y5 x8 s$ y$ O  l8 h# v       }: y, a9 S5 O% Y1 {/ m8 E& n
      cout<<endl;& l- X( F5 J5 |" t
}
2 R1 V8 a2 z- {8 z* T7 `7 E cout<<endl<<endl;
5 c! O; z4 x/ B- I}
& l; T/ b+ L/ A' g; ^( v' t  c' h% C4 k- U0 k" B+ }
void dfs(int x,int y,int step) {2 r' o* K# a& _1 M: v; A  K
if(step> 6) {6 \3 G8 `) G* c
      return ;
0 J5 p7 U" A: o7 N' y7 a }" }1 z9 e9 Z8 P# V- [
if(x == 1&&y == 1&&vis[1][1] == true) {
/ s$ G: r6 P8 ?$ @+ h       ans++;" M1 h9 X% P% A+ G0 T( q% I/ N
      output();/ b* F& A+ k" o$ S- E* O4 T9 V
      return ;& U; _4 k. R# b+ U8 f# i5 J6 R8 Q
}
- w+ q/ u% G$ `+ u for(int i = 0;i< 4;i++) {
. o3 W2 @; T& X! `: N       int tx = x+ne[0];
" X1 P  L, c; x+ j4 ?( \       int ty = y+ne[1];$ I1 B+ s1 o& Q4 \. e( U

; E1 Z4 k  h2 q2 m; d       if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
" r3 `* f. p6 w. ]+ s( q       vis[tx][ty] = true;
& g+ V; D" k6 I% l- Q       dfs(tx,ty,step+1);
& J/ C7 H! K, `% e" d" R- \$ X2 I2 T% z       vis[tx][ty] = false;
; U2 ]6 J* C! k/ ]& k! O* S }
$ ]+ R5 ]; |2 o  y7 s: X1 W" \$ } return ;4 [8 h) Z, Z- x1 A2 @
}
4 F* t3 ]8 G, a+ ]$ y  \% s3 i& L( A; A4 D
int main() {6 q& O# Q4 ]) C7 e
dfs(1,1,0);
+ ]" R1 k5 ?) I2 L$ j, o8 @ cout<<ans<<endl;
5 u( |' ]2 w* q) z) I
3 d  x3 f. q) s  A8 @, o2 U. _ return 0;
* O4 j: p1 y/ a$ W; Y7 \# M}9 \' ~' X! m: f; Z4 C5 g8 e
--------------------- ! [5 W0 a- J9 ~5 O
作者：nka_kun ! K  B2 p6 d/ ^$ c1 a. I; }
来源：CSDN 3 ?- D! d% Q# G1 k3 n
: S. }0 Y* `; G3 {1 N
3 Q' @/ J+ j4 P+ c1 r4 `( n