查看: 1958|回复: 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]<<' ';
      }
0 A7 V: K& t  L1 y7 X6 V1 H1 M       cout<<endl;7 V& A) k/ Y, X( o
}
% g' s% v( [/ {* ]# Q cout<<endl<<endl;2 ~& B: i( E0 @
}
! i; W3 [, G5 E$ x/ `* E7 ~
0 C4 Z( G, r9 A) o/ ivoid dfs(int x,int y,int step) {) ?- J/ Z: v" J+ c9 \
if(step> 6) {
& z7 v1 u( P: W       return ;
) ?# Z+ |) Q; n) W4 f! E }# P  F3 U; J6 r2 y  }# L
if(x == 1&&y == 1&&vis[1][1] == true) {
) y" O% W$ h2 x* [8 D) W       ans++;% H% j& R- x5 B) d8 {3 Y# c) v
      output();+ y3 z/ G. w9 S6 a+ s8 U: a( t
      return ;7 d6 {/ T5 g2 y8 X' E( ~
}
: O+ p# J) H3 K& S" a1 V for(int i = 0;i< 4;i++) {
8 \! A0 f* `9 t. u" N0 r       int tx = x+ne[0];6 f6 u$ I7 g% i' v( k
      int ty = y+ne[1];/ {- ^* w  K5 E6 V6 N6 R( ]+ b

% T( ?% T) o0 n3 v6 @       if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;% X/ t0 q. g: W% c1 J6 K; L4 p
      vis[tx][ty] = true;
  P( v3 U% K  R! d0 |& m       dfs(tx,ty,step+1);1 {$ o  ?; |2 |- D% g. ~
      vis[tx][ty] = false;3 X' f5 p! X3 R# c( L; n% G+ _* R9 O
}
4 ]2 a0 y' S  j4 @ return ;" d- q* e, Z, L2 k# c, _
}/ a8 f) b- q( M& f# ?) k: n% w9 O

3 H" X) C9 a9 dint main() {
! I, G, u8 l5 i+ r dfs(1,1,0);
7 W# Y) T& c# K; I cout<<ans<<endl;
6 }: L0 T8 e: z6 Z4 g$ |9 M5 w* }# }5 ^2 b+ C. Y$ {* E
return 0;
! E' _0 |/ u3 r& l! o. B}
' O; p# F  A4 H# T' X--------------------- + f! q% V6 W- K) w# _
作者：nka_kun
0 a1 ~0 K8 J, k8 I8 r! G* `3 j: n+ o来源：CSDN
* L+ m7 \/ v/ t5 }" Q
2 ?4 Y* D% C7 g- Z1 @! M- w7 R, o  S6 }$ R; E: r