找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2630|回复: 7
收起左侧

[Snapchat] 请教一道snapchat onsite题目

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 11-8-2015 09:05 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 11-12-2015 02:19 AM 编辑
+ h, q# f& r! |; j6 ]
5 t% Y: J: x) N4 [* J& e给了一个N*N的地图,上面有一些障碍物,以及一个起点和一个终点,问从起点走K
2 W) |; U. V$ q6 w& s9 S步正好到终点的路线有多少条,已经走过的地方可以重复走。
' u6 a2 {! L3 i+ ]0 ]4 i. z. h: }. ^

( p: Z& Z8 q( r尝试了几次解法都不对,关键是重复走不知道怎么处理。有谁可以分享下代码实现么?/ D4 x7 \" i; w  P4 _3 j% C

15

主题

2

精华

117

积分

资深会员

Rank: 2

积分
117
发表于 11-11-2015 02:52 AM | 显示全部楼层
码了一个,不知道对不对
5 V& w8 w' P& G3 X! Y* Nstatic int res = 0;
, z* H$ M# V- U* K: p3 s; `$ w        public static int pathNum(int n, int startI, int startJ, int endI,int endJ,int k){1 H$ b) I2 p( \6 t4 S; B+ }
                dfsHelper(n,startI,startJ,endI,endJ,k);  P/ Q( A2 @+ s4 ]
                return res;
- r1 A0 _( I6 a9 Q        }
4 J# J/ X% \. }        public static void dfsHelper(int n, int i, int j, int endI,int endJ,int k){+ l) j. }1 J: S8 `, T' t# [+ h/ C
                if(i == endI &&  j == endJ && k == 0){
# w* W% I6 H, z/ K1 `4 Y0 m6 h! ~                        res++;4 f8 G8 o& o6 D
                        return;) W4 e4 _( J$ M: x7 J0 B( o
                }
2 z+ u  @' |$ x6 e                if(k <= 0 || i < 0 || j < 0 || i >= n || j >= n){
: q- R" ~7 ~" R                        return;- A' z2 |4 d$ r, ]
                }  G3 i. r5 l) J& k
                dfsHelper(n,i+1,j,endI,endJ,k-1);" ^7 g3 ~; w9 H  l( {
                dfsHelper(n,i-1,j,endI,endJ,k-1);: S5 o2 J7 r0 p* ?1 Y
                dfsHelper(n,i,j+1,endI,endJ,k-1);
! h; q/ I- [- }0 b2 s# Z                dfsHelper(n,i,j-1,endI,endJ,k-1);
3 c& |! }  q# |3 L( J' w) v. V        }

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
 楼主| 发表于 11-11-2015 11:12 PM | 显示全部楼层
宝贝忆彼岸 发表于 11-11-2015 02:52 AM
( v6 Q6 X9 w1 R8 n5 ~1 `$ E码了一个,不知道对不对2 y0 x9 Q  _( [2 K) }
static int res = 0;! |* X3 ?. e- o# ]5 i$ J- W
        public static int pathNum(int n, int startI, int start ...

* R; b7 d! x( x) F2 v7 {我测了几种情况都可以通过,应该是对的。
7 V( K5 N* R! B$ ?" u# G2 M
2 l9 a! I! u' H0 X/ T) V% s你知道这题怎么用BFS做么?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表