查看: 1852|回复: 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 j& c1 L$ H0 f! v       }1 H$ e7 n8 E9 [
      cout<<endl;# S3 O& m8 `5 r4 J
}( T8 B) g6 g, S( y6 d1 y9 W$ s/ ^( b
cout<<endl<<endl;
8 w& ~' L6 q. B# g}
, {7 ]% n7 c& o4 C: c' ]/ Y* A5 I: F* }, @  V* u/ V" y% H8 N4 W
void dfs(int x,int y,int step) {
1 `% S$ x8 ^# }0 i if(step> 6) {
+ ]$ I, r" i8 |( L, o+ k8 ?  \       return ;  R7 y. |  y" b7 k+ ~! l% Y
}, P- @- I( _  J% }
if(x == 1&&y == 1&&vis[1][1] == true) {5 Z$ |3 `* s  p6 f' m! I: v  y
      ans++;
. W3 L% S$ {+ j% `7 f       output();  e6 f& p) n/ w) b! t4 i% ^* ?- u
      return ;6 a' {4 e: S9 x* D. w' W7 x* n
}
9 ?9 L/ N2 A& k for(int i = 0;i< 4;i++) {, T  y! u& s3 \7 }- M6 w
      int tx = x+ne[0];& t8 g4 }8 f* X" ]
      int ty = y+ne[1];) c! ~  V& ^- d6 h  W

2 \8 [$ f+ Y! N       if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
; ~* N# V3 F' x$ ~( G       vis[tx][ty] = true;1 M# \, v+ _/ m! x- S  u
      dfs(tx,ty,step+1);
/ [. q( C* a2 K8 [$ Y' r       vis[tx][ty] = false;
# Y5 I* q9 I: H/ u5 I6 N+ V }! s, q1 i- p0 G' k; F0 F* t/ E7 y
return ;" t4 t$ N9 i) d
}* p! U# v# I5 s$ @

6 H) {9 a+ M; ~; C$ R* h: sint main() {; F9 n+ B& _7 f
dfs(1,1,0);
7 O/ i6 V% H! p cout<<ans<<endl;
7 N& Z, H2 \$ s: M1 O9 o) a0 ~8 p( q6 K
return 0;$ P* G! W- k: a1 Z. ~$ P
}
9 B5 C' R% L9 k. W* g--------------------- ) ]+ t# U9 c7 p5 `4 `) V
作者：nka_kun 2 [- t  M5 Q4 r. V0 Y
来源：CSDN
* n! x2 G8 x8 F/ u& o( J% \& M2 Z2 Y1 T$ I* M3 v; @+ L
; j% I, W( k% v