查看: 1898|回复: 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]<<' ';3 t. o% F& A* @  o' i) ^
      }
5 j/ z( t, `3 o* ~5 `       cout<<endl;: w# t4 D9 w) S) o4 @. W* F9 i7 x
}$ g2 [, ^5 p6 K) u8 ]
cout<<endl<<endl;4 J, B, B. m" B
}
, }. Y6 \% A( ^  k; q! Y9 U
/ P3 }$ o2 C  fvoid dfs(int x,int y,int step) {
: ]/ T% n$ k+ ~) F- S5 m if(step> 6) {! S/ t8 y" o. T6 ^9 \1 H( D! u
      return ;
1 S( Q% @9 Z* c }! r/ K* W4 ~6 _$ X
if(x == 1&&y == 1&&vis[1][1] == true) {8 ?' ^% f0 t' `8 p
      ans++;
6 N& f# L- H! d: x1 L! x5 W# ?       output();0 S/ T% B# ?6 H" G- G
      return ;/ W& `, o7 `0 `: Z. a' K. a7 o
}: x3 u  L2 D2 }' k$ Q
for(int i = 0;i< 4;i++) {* i; h" t4 l1 E/ D8 d- \4 X3 ?
      int tx = x+ne[0];2 K1 n" J0 H9 P( ?  R! Z& x
      int ty = y+ne[1];8 v9 }! F, ~; V; |% W/ f7 Z
, l/ h6 u3 }6 o% N7 U, d' U0 t
      if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
5 i7 j( f% H  [# U& P; l  {, ~       vis[tx][ty] = true;
1 K# f# _5 ?+ B! ~$ {       dfs(tx,ty,step+1);
3 a( w, ?3 T3 j  V/ W4 T       vis[tx][ty] = false;! V  O6 ]8 i' R
}
& u9 |) j4 r( p) ?9 s+ C return ;
7 o% d7 O- z$ c# B% T% n; o& e}
+ I+ B, L+ ?. x% ?$ T+ W! P; e( N' r7 ^' Z1 F1 r) {
int main() {% ]; k) s# f: I9 I
dfs(1,1,0);0 L; d1 B$ z7 h
cout<<ans<<endl;
7 C6 b+ i: T3 I2 s, {/ m
$ f' P5 [% D9 E- l return 0;! B- `, R! D' Z7 C
}
0 j4 z/ ~& H" R/ Y8 d  V---------------------
0 d7 }3 x; q3 a6 b' H" d作者：nka_kun
% k; L1 F% g" z来源：CSDN
1 k2 P$ W! K, U
8 D- z1 I) g/ N" Z( Q( Y5 N1 s2 I0 Q7 Y