越南问题谁做出来了？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

越南问题谁做出来了？

越南问题谁做出来了？# Programming - 葵花宝典

a*q2013-03-22 07:03

1 楼

暑假回国买了4个月往返的AA飞机票，
由于签证问题，错了原来的日程，所以就把原来的返程Cancel了。
但是等到拿到签证后，再改签，却说没有同一级别的舱位，要等到十月份。
由于时间原因不能在国内待那么久，只好买了一个单程票回来了。
请问我的那张返程票该怎么办，我不可能十月份回国一次，再把它用了，有没有别的办
法，可以将损失
降为最小。谢谢。

f*s2013-03-22 07:03

2 楼

周末yard sale瞎买了一个marantz tt-151的唱机，回家发现没有手册。这里要是哪位
碰巧有或者知道去哪里搞一个请帮个忙。恶霸倒是有个人买，可是20刀有点贵。

s*52013-03-22 07:03

3 楼

帮朋友发一则博士后招聘广告：
A postdoctoral research associate position is available in the laboratory of
Dr. Sung-Ho Huh at the University of Nebraska Medical Center. The research
theme of Huh lab is on investigating cellular and molecular basis of
progenitor development, maintenance and regeneration using mouse model
system. We are looking for individuals who are interested in working on
understanding mechanisms by which signaling pathways regulating kidney
development, disease progress and regeneration. We focus on (i)
understanding role of FGF signaling during kidney development; (ii)
understanding role of FGF signaling in polycystic kidney disease; and (iii)
exploring possibility to generate nephron progenitor cells. Candidates
should have a good publication record and Ph.D. in developmental biology,
nephrology or related fields. Experience with mouse embryology, complicated
mouse genetics, RNA sequencing, in vitro organ culture are desired.
Candidates should also demonstrate excellent communication skills and have a
strong passion and commitment to science. Interested applicants should send
a PDF file including a cover letter, CV, and contact information for three
references to Sung-Ho Huh at [email protected]
online application link : https://unmc.peopleadmin.com/postings/43922
Huh Lab：https://www.unmc.edu/regenerativemed/research/labs/huhlab.html

s*h2013-03-22 07:03

4 楼

系统是9.10.预装的Movie Player好像在我机子上不能用（附图），右边有一大块花花绿绿的
不知道怎么回事。这毛病在两台不同显卡的机子上都有。有办法修吗？或者有什么别的
播放器？还是codec不好？我就是自动装了三个包，什么moovida-plugins-ugly,
moovida-plugins-bad(这名字哪个脑残起的?)之类.

vi2013-03-22 07:03

5 楼

http://neil.fraser.name/news/2013/03/16/

h*o2013-03-22 07:03

6 楼

可以耍赖不要剩下的一半
或者补一些钱，把剩下的一半华丽的取消掉

【在 a******q 的大作中提到】

: 暑假回国买了4个月往返的AA飞机票，
: 由于签证问题，错了原来的日程，所以就把原来的返程Cancel了。
: 但是等到拿到签证后，再改签，却说没有同一级别的舱位，要等到十月份。
: 由于时间原因不能在国内待那么久，只好买了一个单程票回来了。
: 请问我的那张返程票该怎么办，我不可能十月份回国一次，再把它用了，有没有别的办
: 法，可以将损失
: 降为最小。谢谢。

k*u2013-03-22 07:03

7 楼

唱机用起来很简单，手册没啥用的。。。
调好转速，33 or 45，有的是自动开始，把盘放上去，按开始，有的是手动开始，
自己把那个arm抬起来，放到盘的外圈，轻轻放下就可以了。。。

【在 f***s 的大作中提到】

: 周末yard sale瞎买了一个marantz tt-151的唱机，回家发现没有手册。这里要是哪位
: 碰巧有或者知道去哪里搞一个请帮个忙。恶霸倒是有个人买，可是20刀有点贵。

o*n2013-03-22 07:03

8 楼

try vlc，没mplayer强大，但易用。

花绿绿的

【在 s**h 的大作中提到】

: 系统是9.10.预装的Movie Player好像在我机子上不能用（附图），右边有一大块花花绿绿的
: 不知道怎么回事。这毛病在两台不同显卡的机子上都有。有办法修吗？或者有什么别的
: 播放器？还是codec不好？我就是自动装了三个包，什么moovida-plugins-ugly,
: moovida-plugins-bad(这名字哪个脑残起的?)之类.

b*e2013-03-22 07:03

9 楼

Let me throw in some idea.
Since each diagonal separates a square into 2 triangles,
we can begin by assigning all triangles (for all squares)
a different color.
The problem is then a classical disjoint set problem - if two triangles
share an edge, they become the same color (i.e. the two disjoint
sets are merged). When the disjoint set algorithm finish, the sizes
of the sets is the area/2.
Of course, the outside box should be marked as a color, too. So we know the
set containing the outside is not enclosed and should be exclude.

【在 vi 的大作中提到】

: http://neil.fraser.name/news/2013/03/16/

a*q2013-03-22 07:03

10 楼

由于是学生特价票，他说不能退。改的话也只要在11月份前。
但是我这段时间不可能再取消了。

s*h2013-03-22 07:03

11 楼

thx. 我去试试。不过还是想弄明白这是什么毛病。

别的

【在 o**n 的大作中提到】

: try vlc，没mplayer强大，但易用。
:
: 花绿绿的

b*n2013-03-22 07:03

12 楼

the
An 11th grade student is supposed to be able to work out and
implement a solution in 45 minutes in PASCAL. Therefore, it
got to be a 'simple' solution.

【在 b*****e 的大作中提到】

: Let me throw in some idea.
: Since each diagonal separates a square into 2 triangles,
: we can begin by assigning all triangles (for all squares)
: a different color.
: The problem is then a classical disjoint set problem - if two triangles
: share an edge, they become the same color (i.e. the two disjoint
: sets are merged). When the disjoint set algorithm finish, the sizes
: of the sets is the area/2.
: Of course, the outside box should be marked as a color, too. So we know the
: set containing the outside is not enclosed and should be exclude.

h*o2013-03-22 07:03

13 楼

代理说的话都是放p
补一些钱就可以取消的
不过你知道取消的意思吗

【在 a******q 的大作中提到】

: 由于是学生特价票，他说不能退。改的话也只要在11月份前。
: 但是我这段时间不可能再取消了。

E*V2013-03-22 07:03

14 楼

apt-get install mplayer
[email protected]$ mplayer yourmovie

花绿绿的

【在 s**h 的大作中提到】

b*e2013-03-22 07:03

15 楼

The details:
A[i][j] == 0 means \ (i.e. left triangle\right triangle)
A[i][j] == 1 means / (i.e. left /right )
Given A[0..N-1][0..M-1],
Between A[i][j] and A[i+1][j],
triangle (i,j,right) is connected to (i+1,j,left)
Between A[i][j] and A[i][j+1],
(A[i][j]==0) ? (i,j,left) : (i,j,right )
is connected to
(A[i][j+1]==0) ? (i,j+1,right) : (i,j+1,left)
The outside box is connected to
all (0,j,left)
and all (N-1,j,right)
and all (A[i][0]==0)? (i,0,right) : (i,0,left)
and all (A[i][M-1]==0) ? (i,M-1,left) : (i,M-1,right)
The rest would be standard union-find algorithm for disjoint sets.

a*e2013-03-22 07:03

16 楼

mplayer is not supposed to be used directly
any mplayer gui will make thing much easier
the best so far is SMPLAYER

【在 E*V 的大作中提到】

: apt-get install mplayer
: [email protected]$ mplayer yourmovie
:
: 花绿绿的

b*e2013-03-22 07:03

17 楼

The "outside" part could be dropped since it's easy to tell
that a triangle with a border edge is in open area. That would
simplify things down quite a bit.
But, 45 minutes in class? I don't think many of my students (typical CS
undergrads) can do it without some serious help.

【在 b*****e 的大作中提到】

: The details:
: A[i][j] == 0 means \ (i.e. left triangle\right triangle)
: A[i][j] == 1 means / (i.e. left /right )
: Given A[0..N-1][0..M-1],
: Between A[i][j] and A[i+1][j],
: triangle (i,j,right) is connected to (i+1,j,left)
: Between A[i][j] and A[i][j+1],
: (A[i][j]==0) ? (i,j,left) : (i,j,right )
: is connected to
: (A[i][j+1]==0) ? (i,j+1,right) : (i,j+1,left)

s*h2013-03-22 07:03

18 楼

啊。我以为Movie Player就是mplayer呢。这两个原来不是一回事？

别的

【在 E*V 的大作中提到】

: apt-get install mplayer
: [email protected]$ mplayer yourmovie
:
: 花绿绿的

b*n2013-03-22 07:03

19 楼

Did you read the data file? From the data file, it's not
immediately clear about the triangle stuff, ex the size
of a unit square.

【在 b*****e 的大作中提到】

s*h2013-03-22 07:03

20 楼

让我也搜搜看这个smplayer.3x

【在 a*******e 的大作中提到】

: mplayer is not supposed to be used directly
: any mplayer gui will make thing much easier
: the best so far is SMPLAYER

c*p2013-03-22 07:03

21 楼

这个问题不是在google面试题里排第三么？

【在 b***n 的大作中提到】

:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.

s*h2013-03-22 07:03

22 楼

恩，装了这个，很好。thx.

【在 s**h 的大作中提到】

: 让我也搜搜看这个smplayer.3x

d*a2013-03-22 07:03

23 楼

这问题不复杂，用一个O(N^3)的算法可以解出来...不知道是不是复杂度最优。

E*V2013-03-22 07:03

24 楼

ft, I think mplayer itself is good enough
I always use mplayer in command line mode

【在 s**h 的大作中提到】

: 恩，装了这个，很好。thx.

a*e2013-03-22 07:03

25 楼

从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
单，时间效率就是 O(n)

【在 b***n 的大作中提到】

:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.

a*e2013-03-22 07:03

26 楼

dude, command line is like dinosaur age...
you can still use it but most users would prefer a nice gui in nowadays i
believe, and they don't even care what is behind those nice interfaces :)

【在 E*V 的大作中提到】

: ft, I think mplayer itself is good enough
: I always use mplayer in command line mode

vi2013-03-22 07:03

27 楼

请老兄花半个小时暴力一把。
我看不出怎样暴力。

【在 a*****e 的大作中提到】

: 从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
: 单，时间效率就是 O(n)

s*h2013-03-22 07:03

28 楼

呵呵。我好象也有mplayer。不过即使全屏图像也是挤在中间，跟邮票似的。

【在 E*V 的大作中提到】

: ft, I think mplayer itself is good enough
: I always use mplayer in command line mode

b*e2013-03-22 07:03

29 楼

What's raster image color filling problem? Can you provide a link pls.
Union/find is amortized linear time, and that's hard to beat already.

【在 a*****e 的大作中提到】

: 从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
: 单，时间效率就是 O(n)

U*L2013-03-22 07:03

30 楼

mplayer

a*e2013-03-22 07:03

31 楼

http://en.wikipedia.org/wiki/Flood_fill

【在 b*****e 的大作中提到】

: What's raster image color filling problem? Can you provide a link pls.
: Union/find is amortized linear time, and that's hard to beat already.

h*n2013-03-22 07:03

32 楼

新手的话，试试VLC，老手装mplayer

b*e2013-03-22 07:03

33 楼

Thx. Makes perfect sense. Using graph search is another natural way of
solving disjoint set problems

【在 a*****e 的大作中提到】

: http://en.wikipedia.org/wiki/Flood_fill

r*t2013-03-22 07:03

34 楼

这个是基于 gstreamer 的媒体播放器，所以 plugins 也随着叫了。多媒体里面
gstreamer is the future. 问题是 gstreamer 太大太全了，有 bug 的可能比
monolith player 高。不过 0.10 之后 gstreamer 好了很多。
现在 gstreamer dev 都影响到 X 了，下一版的 X 能直接支持 yuv 视频而不用先转成
RGBA 了。

花绿绿的

【在 s**h 的大作中提到】

s*V2013-03-22 07:03

35 楼

他没说都能用计算机解吧，GRADE11也太难了

【在 b***n 的大作中提到】

:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.

s*h2013-03-22 07:03

36 楼

谢谢科普

别的

【在 r****t 的大作中提到】

: 这个是基于 gstreamer 的媒体播放器，所以 plugins 也随着叫了。多媒体里面
: gstreamer is the future. 问题是 gstreamer 太大太全了，有 bug 的可能比
: monolith player 高。不过 0.10 之后 gstreamer 好了很多。
: 现在 gstreamer dev 都影响到 X 了，下一版的 X 能直接支持 yuv 视频而不用先转成
: RGBA 了。
:
: 花绿绿的

a*e2013-03-22 07:03

37 楼

午饭前闲着也是闲着，写了个 Haskell 程序：
http://pastie.org/7093065
主体算法就是两个函数。
fill 是从一个点开始递归填色，如成功则返回结果地图，如此点不为空，则返回
Nothing。
fill :: Color -> Map -> Pos -> Maybe Map
fill c m p = guard (readColor m p == 0) >>
return (foldl (fill' c) (setColor m p c) (neighbor m p))
where fill' c m = maybe m id . fill c m
fillAll 对地图扫描，对每个点填色，如果填色成功，颜色要递增。
fillAll :: Map -> Map
fillAll m = fst $ foldl aux (m, 2) (indices m)
where aux (m, c) = maybe (m, c) (\m -> (m, c+1)) . fill c m
使用原题的数据文件 http://neil.fraser.name/news/2013/cs-vn/data.txt 运行结果如下：
15555555122218881;;;;;;;1
215555512221618881;;;;;1<
2215551222166618881;;;1<<
22215122216666618881;1<<<
122212221666166618881<<<<
3122222166616661918881<<<
33122216661666199918881<<
333121666166619999918881<
3333166616661999999918881
33316661616661999991:1888
3316661666166619991:::188
316661666661666191:::::18
16661666166616661:::1:::1
4166666171666661:::1:::1=
441666177716661:::1:::1==
44416177777161:::1:::1===
4444177777771:::1:::1====
Color 6 96
Color 9 25
假设 n 是数据文件的长度，因为每个点访问的次数与 n 无关，所以时间空间复杂度均
为 O(n)。

【在 vi 的大作中提到】

:
: 请老兄花半个小时暴力一把。
: 我看不出怎样暴力。

W*u2013-03-22 07:03

38 楼

MPLAYER, VLC ,MOVIE PLAYER 全装, 碟不同, 用的不一样

r*e2013-03-22 07:03

39 楼

你这个不是解。原题是求面积。
96个零很容易数出来，但是换成面积就复杂多了。
这个思路不对，还是最上面找三角的靠谱，
但是前面把原始数据转换成斜杠的一步似乎不方便。

【在 a*****e 的大作中提到】

: 午饭前闲着也是闲着，写了个 Haskell 程序：
: http://pastie.org/7093065
: 主体算法就是两个函数。
: fill 是从一个点开始递归填色，如成功则返回结果地图，如此点不为空，则返回
: Nothing。
: fill :: Color -> Map -> Pos -> Maybe Map
: fill c m p = guard (readColor m p == 0) >>
: return (foldl (fill' c) (setColor m p c) (neighbor m p))
: where fill' c m = maybe m id . fill c m
: fillAll 对地图扫描，对每个点填色，如果填色成功，颜色要递增。

z*t2013-03-22 07:03

40 楼

为什么我的totem player几乎万能，什么都能播，包括高清。没记得怎么折腾过

r*e2013-03-22 07:03

41 楼

用PASCAL，从拿到题到找出解，一个班大多数都可以在45分钟以内完成。

【在 s*****V 的大作中提到】

: 他没说都能用计算机解吧，GRADE11也太难了

W*u2013-03-22 07:03

42 楼

过
Computer condition and Upgrade info. Please!
Thanks!

【在 z****t 的大作中提到】

: 为什么我的totem player几乎万能，什么都能播，包括高清。没记得怎么折腾过

s*V2013-03-22 07:03

43 楼

这肯定不是越南的普通班级吧，如果是什么理科实验班的，专门搞信息竞赛的应该不成
啥问题。

【在 r***e 的大作中提到】

:
: 用PASCAL，从拿到题到找出解，一个班大多数都可以在45分钟以内完成。

S*d2013-03-22 07:03

44 楼

sigh.
不知道为什么很多人很noob的就知道装mplayer呢?
If you are trying to install it on a desktop computer, I would recommend VLC
. It is simple and easy , very powerful (you don't need to install extra
codec and mess with the command line parameters) and does trans-coding
extremely well. If you wanna do home brewed trans-coding, nothing is better
suited.
And windows, mac, linux all have it.

r*e2013-03-22 07:03

45 楼

就是普通班，博客作者是Google负责教育的联系员，专门到越南调查的。
CS老师一个月工资只有$100，他还捐了一年的工资。
越南全民从小学二年级开始学CS，四年级开始编程。
博客中和美国加州数理天才班的水平做了对比。

【在 s*****V 的大作中提到】

: 这肯定不是越南的普通班级吧，如果是什么理科实验班的，专门搞信息竞赛的应该不成
: 啥问题。

a*e2013-03-22 07:03

46 楼

vlc vs mplayer is like vi vs emacs....

VLC
better

【在 S***d 的大作中提到】

: sigh.
: 不知道为什么很多人很noob的就知道装mplayer呢?
: If you are trying to install it on a desktop computer, I would recommend VLC
: . It is simple and easy , very powerful (you don't need to install extra
: codec and mess with the command line parameters) and does trans-coding
: extremely well. If you wanna do home brewed trans-coding, nothing is better
: suited.
: And windows, mac, linux all have it.

s*V2013-03-22 07:03

47 楼

I don't believe, 你知道我们当年在高中以后到了省重点中学才能学计算机。越南比
中国经济要差很多，中国都做不到小学开始学计算机，越南有这个条件么？

【在 r***e 的大作中提到】

:
: 就是普通班，博客作者是Google负责教育的联系员，专门到越南调查的。
: CS老师一个月工资只有$100，他还捐了一年的工资。
: 越南全民从小学二年级开始学CS，四年级开始编程。
: 博客中和美国加州数理天才班的水平做了对比。

z*t2013-03-22 07:03

48 楼

Lenovo T61 intel GM965集成显卡 (被列为intel系列中唯一的问题显卡) ubuntu
从7.10后没有重装过一直
在线升级到10.10
【在 Wuliu (Mimi) 的大作中提到: 】

r*e2013-03-22 07:03

49 楼

您读英文吗？最上面是链接。

【在 s*****V 的大作中提到】

: I don't believe, 你知道我们当年在高中以后到了省重点中学才能学计算机。越南比
: 中国经济要差很多，中国都做不到小学开始学计算机，越南有这个条件么？

r*t2013-03-22 07:03

50 楼

因为 totem uses gstreamer.

过

【在 z****t 的大作中提到】

: 为什么我的totem player几乎万能，什么都能播，包括高清。没记得怎么折腾过

a*e2013-03-22 07:03

51 楼

从数据文件就直接能够看出来是考递归的题，你也不要把问题想太复杂了。
毕竟是给高中生做的题，我那么大的时候 Pascal 很熟练，类似的算法也
实现过，做这个题绝对有把握。
退一万步讲，你要求的面积也是和数出来的零成正比，又有何不可呢？

【在 r***e 的大作中提到】

: 你这个不是解。原题是求面积。
: 96个零很容易数出来，但是换成面积就复杂多了。
: 这个思路不对，还是最上面找三角的靠谱，
: 但是前面把原始数据转换成斜杠的一步似乎不方便。

n*t2013-03-22 07:03

52 楼

最强大的就是 mplayer 了吧，界面用 smplayer:
apt-get install smplayer
俺 windows 里也用这个了，其他 player 都是北卡，哈哈

花绿绿的

【在 s**h 的大作中提到】

r*e2013-03-22 07:03

53 楼

题目上英文和越南话都写了，最后的结果是8（面积）。
你那个算法后面肯定走不通。
人家问的是北京到上海有多少里地，你回答坐火车27站，然后解释
你的答案和要求的答案数值上成正比？

【在 a*****e 的大作中提到】

: 从数据文件就直接能够看出来是考递归的题，你也不要把问题想太复杂了。
: 毕竟是给高中生做的题，我那么大的时候 Pascal 很熟练，类似的算法也
: 实现过，做这个题绝对有把握。
: 退一万步讲，你要求的面积也是和数出来的零成正比，又有何不可呢？

b*s2013-03-22 07:03

54 楼

vlc

s*V2013-03-22 07:03

55 楼

链接怎么样，他也不过是去越南看几天，就能知道全貌？还不是越南当地官员带他看几
个牛逼的学校。

【在 r***e 的大作中提到】

:
: 题目上英文和越南话都写了，最后的结果是8（面积）。
: 你那个算法后面肯定走不通。
: 人家问的是北京到上海有多少里地，你回答坐火车27站，然后解释
: 你的答案和要求的答案数值上成正比？

q*g2013-03-22 07:03

56 楼

建议装深度或者雨林木风linux，汉化和看电影都帮你做好了，省麻烦

r*e2013-03-22 07:03

57 楼

您有时间灌水，倒是没有时间读一下原文，总共没有多少字。
越南官方不允许参观学校的。
这位老兄凭着一张西方面孔，一张Google名片，自己随机找学校往里闯。

【在 s*****V 的大作中提到】

: 链接怎么样，他也不过是去越南看几天，就能知道全貌？还不是越南当地官员带他看几
: 个牛逼的学校。

c*m2013-03-22 07:03

58 楼

这个没什么noob不noob的。
vlc 在我的老机子上既不稳定，放一些codec经常crash. 后来就一直stick with mplay
er了, 基本没碰到过大问题。

VLC
better

【在 S***d 的大作中提到】

s*V2013-03-22 07:03

59 楼

没你们想的那么难吧，
1.先判断是不是闭合的。
2.如果闭合，一行行扫描，从第一列有MAZE的开始，有MAZE的算1/2.
没MAZE算1，到最后一个有MAZE的结束。有闭合区域的MAZE数目都是偶数个。

【在 r***e 的大作中提到】

:
: 您有时间灌水，倒是没有时间读一下原文，总共没有多少字。
: 越南官方不允许参观学校的。
: 这位老兄凭着一张西方面孔，一张Google名片，自己随机找学校往里闯。

s*V2013-03-22 07:03

60 楼

你可以动脑子想一想就是了，Is it possible? 这边专业码农都要花很多时间争论，越
南随便一个高中班级全班都能SOLVE?

【在 r***e 的大作中提到】

r*e2013-03-22 07:03

61 楼

逻辑题啊！
你用了一个隐含前提就是专业码农的智力水平不低于大众平均智力水平。
For the sake of argument, 有些专业码农是别的工作做不了或者做不下去
才不得不做码农的。

【在 s*****V 的大作中提到】

: 你可以动脑子想一想就是了，Is it possible? 这边专业码农都要花很多时间争论，越
: 南随便一个高中班级全班都能SOLVE?

a*e2013-03-22 07:03

62 楼

你难道看不出来是成比例的吗？
较这个劲没意思，我的结果 (96/12, 25/12) 略有出入是因为原数据的格式不是正好
4x4 一格，如果处理一下 (drop every 5th column) 就正常了。

【在 r***e 的大作中提到】

:
: 逻辑题啊！
: 你用了一个隐含前提就是专业码农的智力水平不低于大众平均智力水平。
: For the sake of argument, 有些专业码农是别的工作做不了或者做不下去
: 才不得不做码农的。

r*e2013-03-22 07:03

63 楼

中间有间断线的情况呢？不是那么简单。

【在 a*****e 的大作中提到】

: 你难道看不出来是成比例的吗？
: 较这个劲没意思，我的结果 (96/12, 25/12) 略有出入是因为原数据的格式不是正好
: 4x4 一格，如果处理一下 (drop every 5th column) 就正常了。

a*e2013-03-22 07:03

64 楼

你这个说的对，给的数据是 25x17，但是图上画出来 6x4，硬要扣题则需要自己提供正
确数据。比如 2x2 表示每一格。
10 表示 \
01
01 表示 /
10
总的来说，编程题考的是算法和思路，这个对了就行了。

【在 r***e 的大作中提到】

:
: 中间有间断线的情况呢？不是那么简单。

d*a2013-03-22 07:03

65 楼

赞实证。
用原题的notation，复杂度是O(M*N)吧。也可以说是O(N^2)，假设M<=N。

...

【在 a*****e 的大作中提到】

b*n2013-03-22 07:03

66 楼

这题不就是uva 705么。从maze建matrix要稍微转个弯，然后一个简单的dfs就搞定了。
这应该算是国内搞OI和ACM都会做的基础练习。越南这个如果就是随便一个普通高中的
话，还是挺有实力的。

【在 vi 的大作中提到】

: http://neil.fraser.name/news/2013/03/16/

r*e2013-03-22 07:03

67 楼

xiexie!
我还是观察不细致，没有看出来是迷宫。
既然是迷宫，就不需要dfs，主要keep making left turns就可以了。
uva是个什么东西？为什么这么有名？

【在 b*****n 的大作中提到】

: 这题不就是uva 705么。从maze建matrix要稍微转个弯，然后一个简单的dfs就搞定了。
: 这应该算是国内搞OI和ACM都会做的基础练习。越南这个如果就是随便一个普通高中的
: 话，还是挺有实力的。

b*n2013-03-22 07:03

68 楼

google uva online judge 705. 题目就叫slash maze. 写完code自己submit 一下就行
了。

【在 r***e 的大作中提到】

:
: xiexie!
: 我还是观察不细致，没有看出来是迷宫。
: 既然是迷宫，就不需要dfs，主要keep making left turns就可以了。
: uva是个什么东西？为什么这么有名？