数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第五题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:58
标题:
2019第十届蓝桥杯B组决赛题解第五题
2019第十届蓝桥杯B组决赛题解第五题
: u9 \* z+ q+ v# }/ X
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数
, I9 k8 l" y/ {0 _% H4 w' Q
直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了
& Q& j+ L, Q" i- M% g. }& A. {
结果: 208-2=206
& @5 a4 Y' N& x! ~3 y
代码:
& z, P; D, z0 G) j# m3 u
#include<bits/stdc++.h>
+ T6 t8 @) y& V
#define mem(a,b) memset(a,b,sizeof(a))
5 D* v7 {8 o1 W$ m& j, m% T3 v
using namespace std;
6 J0 O+ e0 h0 P3 b
typedef long long ll;
! d3 h. T# }( K! j, x
const int inf = 0x3f3f3f3f;
' z4 ?- H- M/ [
const int maxn = 3e5+55555;
3 C/ H3 o, h; U" G$ v
const ll mod = 998244353;
# j; U! v. [0 K. [2 e
const double eps = 1e-7;
) q. _1 l7 f0 N: p/ L& q+ `6 L
( x( x; p: n8 W5 P+ t7 _ E
bool vis[10][10];
, k$ n; R0 X* {
int ne[4][2] = {1,0,-1,0,0,1,0,-1};
" d( k. w y) z$ i4 x, I
int ans;
( ^, T; {7 Y. |$ R8 R
) a. k" U; K$ g/ A3 \0 x7 _
void output() {
# f6 q1 [# S- A" y1 [
for(int i = 1;i<= 6;i++) {
2 W/ ~, Q* o W- A6 Y0 J- t, E& a
for(int j = 1;j<= 6;j++) {
' _! N" r: O' m8 q* }* U$ d% C
cout<<vis
[j]<<' ';
' @$ S/ P$ {9 ~$ v$ X1 Q( Q
}
% a+ k8 z3 i+ G5 |( g
cout<<endl;
5 U/ T# G0 [8 P5 D( I1 e
}
3 D/ J& y0 L8 f. M4 ~8 `0 i
cout<<endl<<endl;
/ ]6 l8 [; V5 U, l' ^5 x
}
/ Z6 B% i7 n3 s5 N- `
# r4 E9 o3 P" H, R
void dfs(int x,int y,int step) {
) G/ H& Q# \* V0 z9 o# g( x" Y1 ^; y
if(step> 6) {
3 y5 S9 y/ h" D
return ;
7 t9 Z% P4 m; E P ]& y9 P* D2 H$ v
}
! _3 A: @! c- F }# Q3 G; @3 G
if(x == 1&&y == 1&&vis[1][1] == true) {
! }. O* Q/ L/ w4 j/ |) g+ O
ans++;
0 d2 b& c3 M# G! o$ G7 u: S4 y) ~/ |/ u
output();
: E/ U6 t7 H3 E& W( ?( j
return ;
2 G ]6 t$ a% a# u ^5 o
}
. Y9 E6 B# z: s8 K0 P
for(int i = 0;i< 4;i++) {
: l& M" p4 B2 e
int tx = x+ne
[0];
8 S# ` _# ^# }2 R" U- j
int ty = y+ne
[1];
( n2 C8 |" M# d( E
/ g& O( N3 ~ T3 z# u
if(x> 6||y> 6||x< 1||y< 1||vis[tx][ty]) continue;
& w8 \' x1 d' K/ \8 @* B
vis[tx][ty] = true;
( n+ d. y( \7 P Y" w6 d M
dfs(tx,ty,step+1);
- u$ G6 i" d5 I P. c
vis[tx][ty] = false;
- e& y5 |3 V0 k( W K' J7 G$ l- s
}
& T% q3 J. c* z \
return ;
5 P# z& X v4 d8 M$ K* d
}
$ Y" y/ e5 s# W" Q l
1 {0 [: J6 h$ |1 k/ E: h
int main() {
a' W8 n1 |# q( o6 h6 s0 Z* U
dfs(1,1,0);
$ f) E" y( M9 m- T. |0 z) A
cout<<ans<<endl;
, t! ]9 Z! q7 u2 g6 G
" D' ]; ~9 H; _/ L0 p7 M4 D1 b
return 0;
Q) B% T: f3 {
}
" x9 c1 p5 s& ?* d: i% F
---------------------
* p$ s# h# r: B1 k( L$ }
作者：nka_kun
" Y+ @: V7 T$ b. E+ T
来源：CSDN
0 z! n- ~' X; |4 u
" c* ?" U0 `9 D( Q; E: Z0 d
% [ K; H q, ?6 L' Q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5