查看: 1957|回复: 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]<<' ';
1 j& d" [3 n4 S/ l8 D       }
" @* F2 q% B+ u/ [& O+ P  Z       cout<<endl;/ s! \1 f; e4 G. Y
}
+ P4 H% H  c; G3 L! c. r cout<<endl<<endl;: m7 M, _0 u3 i4 p. t% j0 p' Z
}
6 J( x0 Z9 g! _% O
; V$ X/ N" ~: }" ^  \3 P. H9 u' M1 Bvoid dfs(int x,int y,int step) {# j2 g9 h/ \/ ^/ x
if(step> 6) {
7 E/ }: ^0 ~3 I& V& }( ]/ u       return ;
0 c* a: `% i1 j: [ }/ {1 X# {# F1 `; k9 w* a
if(x == 1&&y == 1&&vis[1][1] == true) {$ a% o4 _" F! J+ `
      ans++;( d; ?) o* L; c$ N: C- E
      output();
  }, _3 l9 J- A4 z       return ;) U% z$ S4 n, Y0 A3 r) M
}
3 h  R1 N. x0 y. u0 }' D for(int i = 0;i< 4;i++) {
: c: g3 H# U- s# h1 A* p; k7 t       int tx = x+ne[0];% n& D) s+ t+ e
      int ty = y+ne[1];
- b) r) m9 h- N$ r+ m8 D+ V. A9 U* y  s8 j" `" @0 y$ |
      if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;! U# H7 Y# j% Z* `8 C
      vis[tx][ty] = true;
9 b& O' f. k6 d0 U" v       dfs(tx,ty,step+1);0 Z" H7 e4 p+ ^& m! h5 S
      vis[tx][ty] = false;0 \9 D- |( S+ s3 k( ?9 k
}
% W5 f6 a: K' C0 X return ;
( ]$ N  x  a% @}
% |8 Y4 _) E* }# l3 S0 z3 ]
. \4 x2 {/ }' ~int main() {
+ E. y7 F  e: R0 ]+ g dfs(1,1,0);* T% z! v7 _) R, g! v; X5 ?5 v
cout<<ans<<endl;
, N# N$ R" M6 y$ _9 y- H' N3 ~6 \; C
return 0;0 P' J" Q# q9 C
}' |; P* V  i7 X: {
--------------------- " D% a' e: r  Z  v9 }" e3 Q) x1 ^
作者：nka_kun
, D9 N1 x" j& E) s8 q来源：CSDN 2 a6 N3 a3 S) |( w% f) H

7 L' D7 l$ Q$ C, j3 s" j% s2 n* a4 K* _* r