翻译了ClipGrab的官方网站


ClipGrab是一个下载和转换网络视频的开源软件。

我最早知道这个软件是因为要在Arch Linux上面下载Youtube上的视频。后来翻Arch的仓库,找到了这东西。界面很简单,使用起来也很称手。后来看到网站上说要招翻译,于是乎就去应招了。

目前语言选择的地方还没加入简体中文,不过可以从这里去看我翻译好的中文页面。

回味FAD 2011


题目中的这个FAD不是黄素腺嘌呤二核苷酸,而是Fedora Activaty Day。LinuxToy上呼吁参与者稍微写一些感想,我也觉得确有写一些东西的必要了,于是就把这篇短文写了出来。

老实说,作为一个学医的,平时就不算太闲,最近更是相当繁忙的一段时期,本不应该抽空去FAD这样的“没用”的东西。然而我实在是很想找一段小小的空闲,暂时忘却一下现实的重压,寻找一点或许是虚假的、稍纵即逝的快慰。因而虽然里面的多数东西我都听得半懂不懂,却仍旧挺高兴,挺感动。见到了 @CSSlayer 仁兄以及在各种虚拟空间神交已久的诸君,觉得难得有一天如此开心。

 

可惜的是我的抒情功底实在太差,所以无论我如何安排,下面的记叙总还是免不了流水帐:

上午的内容我不想再赘述了,就在我写这篇网志的时候,我看到CSSlayer仁兄的FAD回忆网志写好了,可以点击这里去参考他的。对我等来说,下午的内容才是重点,也是真正的FAD内容。

本次FAD 11是和开源软件周合办的,所以下午的小会同时有多个内容并行。按照CSSlayer仁兄的说法,我所在的那个屋子是个Geek聚集地。是不是Geek我不清楚,不过大家基本上都是开源软件的爱好者。虽然专攻不同的领域,但也算是志同道合,相当愉快。不过就内容而言我只记了个大概,具体内容则是忘得差不多了。 @Tiansworld 和 @黑日白月 (Tommy He)兄讲翻译的时候提到了Qt Linguist,是我刚好想学一学的;CSSlayer仁兄讲的是plasmoid开发,这东西讲不了啥实质性内容,只是介绍了一些概况和参考,不过让我印象深刻的是貌似每次不论讲了啥,都能吸引点人去玩玩KDE,看来广告/代言真的是很重要的; @jcome 仁兄讲的是一个2D动画制作软件,大概是想找Flash替代品的人的福音,但说实在我已经多年不玩动画制作了;最后 @alick 仁兄关于TeX Live的演讲我也听了一些,因为我一直想研究下TeX但一直没有时间。另外还见到了Calligra的开发者之一—— @yue ,他居然平时用Qt Creator(据本人说是因为KDevelop打开大工程太慢,跑不动),虽然没聊几句话,但都很愉快。

结束的时候发纪念品。对于纪念品这东西,其实我还是蛮在意的,倒不是贪那点小便宜,只是为留个念想。最后拿到了一张fedora15 64bit的光盘,心想以后大概还能恢复系统用。

也许是因为来得相对早,我很幸运地拿到了中午的饭票,吃了顿比格批萨。虽然没有像有一次同校聚会那样暴饮暴食,不过也算是吃得相当满意了。晚上去了个小地方,虽然作为一个学医的,我对那些触目惊心的卫生细节表示有些难以接受,然而最后还是吃了不少东西。另外晚上去吃饭的时候跟若干同道边走边聊,了解到大家都有尝试各发行版的辛酸史。吃饭的时候也跟他们聊了聊闲话,还是蛮轻松的。

另外还有个小插曲,CSSlayer仁兄把耳机落在了会场,结果他手机恰好没电,于是乎他本来都回到学校了,又折返回来拿了耳机,后来我跟他一起离开了吃饭的地点。

 

基本就是这样了吧……引用某人的一句话:“如果我有什么忘了说的,就当我没说好了。”……

Fcitx皮肤查看器(fcitx-skin-viewer)最后的更新


fcitx-skin-viewer的最后更新

fcitx-skin-viewer的最后更新

Fcitx的皮肤预览功能已集成进Fcitx的KDE控制面板(kcm-fcitx),故fcitx皮肤查看器已无再更新的必要。于是我将最后一个没写完的功能写出,作为最后一次更新的内容。以后我可能会继续更新kcm-fcitx中的皮肤浏览功能。

更新内容:
增加皮肤选择表格,可一键选择当前用户皮肤目录(~/.config/fcitx/skin/)下的皮肤。原有的打开特定皮肤的功能依然存在。

本想至少先汉化一下这个程序,不过最后也没搞定cmake下Qt程序的汉化问题,只得作罢。

Fcitx皮肤查看器


虽说私很懒,不过不忙的时候还是会捣鼓一些东西的,这Fcitx皮肤查看器就是私最近主要在弄的一个。工程方面基本是CSSlayer仁兄打的底子。
配置读取部分是直接调用Fcitx的API,且貌似Fcitx4.1的皮肤配置有所更改,因此应该至少要求Fcitx版本号高于4.1。
虽说只有最基本的功能,输入框还没有写好,边栏还只是把东西一股脑地显示出来,不过大体的形态已经有了,先发出来做个预告。

Fcitx皮肤浏览器

Fcitx皮肤查看器

有兴趣的且有Qt的人可以从github上抓下来玩玩(虽然我认为应该没多少人有兴趣……):
git@github.com:csslayer/fcitx-skin-viewer.git

用C语言重写的会员卡管理程序,欢迎Linux众测试


终于重写完毕了,不过Bug肯定很多,欢迎诸君测试。由于未在Windows下调试,且有磁盘读写的相关代码,若有热心的Windows用户想通过源代码编译还请自行删除可能产生的垃圾文件。

Linux用户可用的二进制程序:

https://skydrive.live.com/?cid=D40A6A1CE1A272AC&id=D40A6A1CE1A272AC%21507&sc=documents

源代码在此,欢迎给出指导:

http://github.com/ukyoi/cardmanage

我不太会用github,所以有些混乱,还请原谅。

[转载]新浪微博你让我浑身发冷


作者:virushuo 发表于 2011-06-09 16:06 最后更新于 2011-06-09 21:06
版权声明:按照by-nc-sa的cc协议可转载,拒绝采用“独家” 授权媒介(含网站和平面媒体)转载、引用、链接,除非获得本人许可。转载时请务必以超链接形式标明文章原始出处和作者信息及本声明。
http://blog.devep.net/virushuo/2011/06/09/post_81.html


 

——
本文特别声明,本文和其中使用的图片均可任意转载和使用。感谢传播。
——

新浪做为中国最早的在美上市互联网公司,一直在诚信方面有不错的口碑,美誉度较高。很多事情人们甚至会替他们辩解,在中国开个公司不容易,要多往好处看。所以今天发现这个公司可以无耻到这么彻底的时候,确实让人发冷。

事情的起因很简单,google的新闻站谷奥发现一篇译文被新浪科技抄袭,这里说抄袭是有证据的,因为就连谷奥翻译错了的地方,新浪科技也照单全收一字不差还原错误翻译。这是一个基本的常识,大家都写对了那是正常的,如果错都能错成一样,那显然是有问题。 谷奥列出新浪抄袭证据的原文在此 ,有兴趣可以仔细看。

这事情只是个开头。后面的才精彩。一般来说这种事情行内多了去,大家抄来抄去,被揪住一次也就嬉皮笑脸道个歉,被抄一方也不会在追究,也就过去了。奇怪的是新浪这次用了一个奇怪的方法,把这个事情弄的越来越大。

首先是新浪科技的编辑骂谷奥傻逼(这在后面新浪科技发的官方声明中变成了”新浪科技编辑骂了两个字母进行回应”),然后总编辑陈彤在微博痛骂谷奥,引起大量用户评论数百条,这些评论先被删至剩30条,随后又恢复,转天这条微博也被删。不过这里有截图

转天谷奥创始人到新浪沟通抄袭事件,新浪仍然拒不承认抄袭。至于”错都错的一样”这种铁证,新浪装作没看到。之后的事情更加戏剧。

新浪科技发了一篇新闻,表示自己绝无抄袭。这篇新闻的留言中凡是对新浪不利的言论一律不显示,只有几条夸新浪的留言显示出来。之后干脆关闭了评论。这篇新闻的结尾是:”新浪科技频道重申:感谢社会各界一直以来的大力支持,欢迎大家继续对新浪科技的工作批评、指正。”,这虚伪的像个笑话,人家批评你们骂人家,新闻评论都不敢开放,还好意思说欢迎批评。

很快,新浪微博小秘书威胁谷奥官方帐号不要造谣,最终结果是谷奥官方帐号变成了号称先审后发,其实不能发表状态,之前发布的和此事相关的微博均被删除或隐藏。谷奥是加V认证的帐号。

事件简要回顾完毕。

这个事件的谷奥一方,是一个只有2个人的个人网站,另外一方是市值近70亿美元的上市公司。这样的实力对比下,新浪从高管到员工,倾全力打压一个个人网站。原因只不过是谷奥对被新浪抄袭事件要个说法。这种底气的来源大概就是微博的发展,新浪已经可以认为,我打压你,你无法还手。

以往人们在媒体无法表达的事情,可以在自媒体和sns表达,如果新浪垄断了微博,将来只要你和新浪有冲突,或者你的东西被新浪看上认为可以盈利,你在自媒体也就出不了声了。新浪产品线复杂人也多,谁都有可能不留神和他们发生冲突。

之前作家和百度的维权事件,新浪微博是主战场之一,但新浪爱问同样盗版他们的小说。如果作家们质疑一下爱问,恐怕结果也是被封杀。诸如此类的事情,以前有不少,以后会发生的更多。比如一家基于新浪做SNS游戏的公司,新浪自己想抢你的业务,你会没法还手,没法出声。所有在新浪微博培养的关系,粉丝,声誉,都不是你的资源,而是新浪的。只不过是对方看你还不算讨厌,暂时让你存在而已。一旦和新浪有冲突,这些都没了。现在看好新浪,爱微博的人,如果有一天发现自己的利益被新浪所占,又无处申诉,感觉会怎么样?这种事情之前也发生过,恐怕除了当事人,别人都没注意,比如新浪微博曾经强制收回大量特殊微博账号 ,这些叫做微招聘,微公益的帐号,起初都是因为用户对这个平台的热爱而自己注册和维护的,做大之后被强制收回。关于这个事情,可以看微公益帐号创造者所写的事情经过:新浪”微博强拆”,拆走的都是用户的心 。这是发生在今年3,4月份的事。

在这个事情之后,所谓的新浪微博开放,做为开发者的我是不会再相信了。新浪科技和谷奥只是义气之争尚且如此,利益之争会如何?一个平台,丧失了中立理性和宽容,不能面对自己的错误,无法改正,乱用资源和强权,一定不会成功。毕竟互联网还是一个存在充分竞争的行业。

如果新浪微博真的垄断了这个行业,未来他的业务线一定会和你发生竞争。微博和以往的SNS不同,是工具也是媒体。一般来说人们碰到不公可以寻求媒体救济,但在新浪这,你没机会。在媒体和舆论上会成一边倒的状态。看这次新浪科技的声明,内容完全不真实,但被攻击的一方只是个人网站,没办法找到一个话语权对等的平台回应。无论你是什么样的名人,都没机会。目前在新浪平台受益的人,都应该好好思考一下如果这样发展下去,你的未来是什么。投资人们,如果你的项目被新浪先看中,如果你们的项目被新浪山寨,做营销的,如果新浪想自己赚营销这笔钱,做自己的营销平台,创业者,你做的产品被腾讯山寨的时候你可以骂,将来被新浪山寨了,你怎么办?…在新浪微博平台上,你们拥有的资产,都在新浪老大哥的垄断之下,剩下的无非就是什么时候杀你这只肥猪而已。最后你最多像已经没法发言的@谷奥现在做的那样,把自己的文章链接写在bio中,新浪真是欺人太甚。

这样的未来,让我浑身发冷。中国之前任何一家互联网公司,无论是百度还是腾讯,都没能把事情做到这么绝,就算是腾讯,也不会因为用户在QQ中交流对腾讯的不满而封掉用户的发言权利。我始终认为,microblog应该是一种协议而不是一种工具。这种工具应该打通几家,而不是被一家拥有。就像邮箱一样,协议和产品需要分开,你可以用新浪邮箱我用gmail他用网易邮箱,我们互相能收到对方的消息,而不能是必须大家都去用一家的邮箱。我觉得如果实在不行,搜狐网易饭否联合吧,打通你们的API,让用户流动起来,别坐等被人各个击破。

为了不让这个一家垄断的未来成真,现在能做的就是力图让几家竞争者平衡,至少应该留下足够强的竞争力量,所以我呼吁停止使用新浪微博,转向腾讯,饭否,网易,搜狐。这个行为看起来有点赌气,可是想到未来,这是为将来的自己留后路。就算你不想那么多,现在开始给自己在其他几家的平台上培养一些资产,留作备份,也是应该的。也就是说,无论你是否停用新浪微博,如果你觉得这个自媒体平台有意义,那就应该立刻把几家全开了,一起用,这样你才能安全,至少将来还有渠道说自己要说的话。

在现实世界我们已经充分体会到了一家独大没有竞争的后果,幸好在虚拟世界,现在你还有机会亲手改变。
====================================

下面这两个badge是我的选择:


我把他们放在blog侧面,就算为多样化的未来出点力。你的选择?

ps,为了实践我的建议,除了twitter,本人恢复更新网易微博 @virushuo 饭否 @virushuo 我还会开国内其他几家的。每天均花一些时间真人更新,同时无限期停止更新新浪,并求新浪删我帐号。大家墙内见。

Ubuntu 11.04 Release Party


由于谷歌地图给的车站位置不是很准,所以迟到了若干分钟。具体的困难就不说了……

算了还是说一说吧……首先我参考了两条路线,但是谷歌地图给的位置不准,于是乎只找到了一条线的站牌。由于和同学一道吃饭,吃完饭就点晚了,本来就很着急,结果等车时我眼睁睁地看着三辆我没找到站牌的那路车先后驶过,自己要等的不见一辆。我寻思这样不行,得找到那一路公交车的站牌。就在我走了一站地之后,我刚才一直在等的车出现了……

不过到得还不算太晚,看到了计算机科学屠戮者大神。让人觉得幸运又诡异的是第一排居然还有座,于是我当仁不让……

下面开始记录内容:

第一位基本没听到,听到的主要是他没少黑Unity——其实不算黑,因为本来Unity问题就很多——此外貌似他也不咋喜欢Gnome3,至少不喜欢现在的Gnome3。并且一定不认为“用户的言论毫不足虑”。大概是因为讲得不是很有趣,底下非常非常乱……但其实我觉得内容倒还有点意思。

第二位是苏大神的“一个菜鸟的爬行轨迹”,从他的演讲内容来看显然不是个菜鸟,因为他居然曾经直接把OpenFetion的代码翻出来然后“翻译”了。讲的内容主要是跟他相关的翻译问题。吐槽点甚多,而且居然好多我都知道……另外貌似这是“山东口音”?

第三位……嗯……首先更正一下上文的一处。事实是除了苏神那个充满山东腔的演讲不是很混乱以外,后面的演讲都很混乱,甚至包括人都走了一大半的下半场报告。第三位是叫做Levin的研究生(大神?),OpenFetion的发起人,很让人无语的是演示居然是全英文的(当然是用汉语讲的),而更让人无语的是苏神吐槽的时候就提到OpenFetion把汉字直接写进代码以至于给本地化带来了大量问题……
主要讲了他自己开发OpenFetion的过程,以及OpenFetion的一些技术细节。OpenFetion居然是用反编译得到的飞信协议的代码,不知道中国移动会不会告他……

第四位……计算机科学屠戮者大神……KDE4.6终于上场了……一开始居然让我们看到了启动列表……乃居然没在本地装kubuntu……
演示居然也用的英文(难道这是当今的趋势?)……不过显然要好看得多,因为图多,当然更重要因为KDE4漂亮……也许更重要的是有魔法少女小圆的壁纸?让我很搞不懂的是大家为啥对ACG如此敏感……当然也有人对屏幕右下角的照片很敏感。
首先浏览了KDE的历史……我是从4.2开始用的,看着很有一种熟悉的感觉啊……从休息时候的聊天来说貌似还算卖成功了。不过我个人认为从讲解的过程来说基本还是幻灯较多,实际演示较少……并且最后把KDE弄成类Unity界面的时候因为屏幕显示的原因,左面一列没有显示出来。其实KDE的效果应该用更多动态的效果来展示……当然还有krunner这样低调绽放(quietly brilliant)的组件……
当然我个人觉得最后这演讲是整个release party里面最好玩的。和第一个讲Unity的对比来看算是丰富得多了。因为Unity本身也没什么可讲的。而KDE众多的功能、软件绝对不是一时半刻能说完的。

课间休息……

下半场……貌似主题是Bug回报。一个是讲了一些中文ubuntu的问题,一个是怂恿人们积极、高水平地回报Bug,甚至还给我们演示了一下如何用调试代码来查kernel的Bug,不过我怀疑此人逻辑有点问题,前面说报Bug态度不能太差,后面又说在邮件列表舌战很有趣……

//

最后……其实我的化学书还没啃完,英语网测还有好多没做,英语单词还没背。不过有这样一个参加的机会实在是很难得啊,于是乎还是来了。怎么说呢……算是不虚此行吧,至少还索取了个10.04(居然不是11.04)的光盘呢……

触摸板异常及用downgrade降级Udev


前几日私在推上发牢骚,曰“进来命途不顺,Arch升级愈升问题愈多”,计算机科学屠戮者大神反问:“此岂非生活之常态?”。其实真的不是生活的常态。也许是私当年用惯了kubuntu(呃……一不留神又黑了kubuntu啊,话说私过几天还要参加release party呢),觉得Arch简直是一个稳定得令人惊讶的系统。唯一的一次问题是源于私穷折腾时的操作失误。在此之前还真的没有找出任何的问题。

然而一次升级过后悲剧发生了。重启候发现触摸板无法使用,遂接上外接鼠标查找原因,计算机科学屠戮者大神说可能是内核的问题,然而私在本地未找到早先留下的包,作罢。后来开机时发现触摸板反映很怪,有时认不出,有时能认出,还有时会认成鼠标,查Xorg的Log,发现自己的EasyCamera(摄像头)被认成了触摸板,然后自然发生错误,于是触摸板的驱动就自动Unload了,没有挂载在正确的地方。去Arch的论坛找,发现貌似是新版本Udev(167-1)的问题,降级回去就可以了。

不过私依然没找到遗留的老版本的Udev包,难道真的要编译才能解决吗?后来看到Bug Report下有人提到可以用AUR里面的叫做“downgrade”的包(名字真直接)。下载后只需用downgrade xxx命令,就可以找到xxx软件的一些早先版本(Udev貌似保留了十多个早先版本),选择一个降级即可,操作非常傻瓜,避免了因误操作可能出现的各种问题,很适合私这样的初学者使用。

后记:

私降级后就把Udev放到升级忽略列表中了。然而今天升级之后发现有个叫做“initscripts”的包要求Udev版本高于167。Google之,发现和启动初始化有关(貌似是废话,嗯……因为细节私也没太看懂)。难道就是因为Udev和这个包的版本不匹配才出现的问题吗?一会可以试试看。

后记的后记:

果然跟此事有关。今日在Arch官网上找到了这句话:

We would like to remind everyone that initscripts expect all other packages (except for the kernel) to be up-to-date. This in particular includes udev, mdadm, dmraid and lvm.

于是升级一下就一切都好了。

Arch恢复


首先感谢计算机科学屠戮者大神,在私的PC上大大地展现了一番bash功力。当然他自己未必觉得如此,但私看得却是眼花缭乱得很……

其实不能挂载的症结就是私grub配置不知怎地(反正绝不是私搞的),挂载root分区那行里的“ro”莫名其妙地变成了“rw”,以至于root被挂载为读写模式,而Arch自检的时候要求挂载为只读模式,于是就出现问题了。

而这个问题说到根上,都是源于私换驱动的时候用了“pacman -Rns catalyst”的命令,以至于pacman把其依赖——xserver卸掉了,于是乎装了啥驱动也不管用了。

另外其实原先私fstab还有个问题,就是swap挂载写了两遍,所以每次启动会提示swap挂载有误,这次也一并解决了。另外还对系统进行不少小调整,在此不一一赘述。

总之很感谢计算机科学屠戮者大神,不过私想到以后如果再有这样的问题,凭自己这样的能力,大概是解决不了的吧。还是得再研究再学习啊。

DFS解迷宫的一些想法


写在前面:私不是程序员,也不是学信科的,也只是最近开始没事的时候翻翻C语言的书。因此阁下很可能会觉得下文所述的想法很原始或是阁下早已用过了。私在此只是记录一下自己的想法。

现阶段私学C语言用的书是宋劲杉的《Linux C编程一站式学习》,里面讲深度优先搜索的时候讲的是个走迷宫问题,用1表示墙,0表示路,从左上走到右下。代码如下:

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5 

struct point { int row, col; } stack[512];
int top = 0;

void push(struct point p)
{
    stack[top++] = p;
}

struct point pop(void)
{
    return stack[--top];
}

int is_empty(void)
{
    return top == 0;
}

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void print_maze(void)
{
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++)
            printf("%d ", maze[i][j]);
        putchar('\n');
    }
    printf("*********\n");
}

struct point predecessor[MAX_ROW][MAX_COL] = {
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};

void visit(int row, int col, struct point pre)
{
    struct point visit_point = { row, col };
    maze[row][col] = 2;
    predecessor[row][col] = pre;
    push(visit_point);
}

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0)
            visit(p.row, p.col+1, p);
        if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0)
            visit(p.row+1, p.col, p);
        if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0)
            visit(p.row, p.col-1, p);
        if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0)
            visit(p.row-1, p.col, p);
        print_maze();
    }
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        printf("(%d, %d)\n", p.row, p.col);
        while (predecessor[p.row][p.col].row != -1) {
            p = predecessor[p.row][p.col];
            printf("(%d, %d)\n", p.row, p.col);
        }
    } else
        printf("No path!\n");

    return 0;
}

大概意思就是每次弹出一个栈,找到周围所有的合法步骤然后把它们栈压进栈区,下一轮时再弹出最后压入的栈,如果走入死路就再次弹栈,找另外一条可能路线,直到找到迷宫的解。如果栈空了就说明无路可走,打出“No path !”。
但是找到解之后就比较麻烦。如何输出路径呢?这段代码使用的方法是建立一个predecessor数组,用来表示每个点的前趋,然后从最后一个点顺藤摸瓜往前找,逐渐打印出来。但这个predecessor数组占用的空间很大,且只能从后向前找,不便于找到其中的某个特定步骤。怎么解决这一问题呢?作者宋劲杉出了一道思考题,还问读者能够想出几种方法,可见方法是不止一种的。

在正确理解这段代码之前,私一直认为栈区中至少应该存有正确路径走过的所有的点,后来才明白这个想法是有问题的。由于每个循环开始时栈顶已经弹出了,此时如果再在这一点继续向深处找,新压入的栈就会把刚才弹出的栈顶覆盖掉,这样找到最后整个栈中在极端情况下(例如整个迷宫都没有岔路)可能一个点也不剩。此外一个循环内是4个方向均会搜索,所以如果有岔路,就会压入多个点,但弹出时只会弹出一个点,所以栈中会残留错误道路的点。

怎么修改呢?其实很容易。原来每个循环会从栈顶弹出一个栈,其实找到路径之后,完全可以把这一栈再压回去,比如这样:

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0) {
            top++;
            visit(p.row, p.col+1, p);
        } else if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0) {
            top++;
            visit(p.row+1, p.col, p);
        } else if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0) {
            top++;
            visit(p.row, p.col-1, p);
        } else if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0) {
            top++;
            visit(p.row-1, p.col, p);
        }
        print_maze();
    }

    int i;
    if (!is_empty()) {
        for (i=0; i<top; i++)
            printf("(%d, %d)\n", stack[i]);
    } else
        printf("No path.\n");

    return 0;
}

如果找到了可用的路,由于有了top++,相当于仅仅是读取到栈顶的数据(而栈没有弹出),这样在搜索路径压栈的时候就不会把原来的栈顶覆盖掉,从而保证了栈中存在所有正确路径上的点。解决残留错误道路的点的问题也很容易,只需让一个循环内如果搜索到了一条可以深入的路径就停止(用else实现),否则再搜索下一条路径。如果找到死路栈会逐个弹出,直到岔路口,所以不用担心找不到正解。到最后如果迷宫存在解的话,栈中所保存的就是正确的路径。由于例子中的“栈”是一个数组(当然您可能会反驳说这个例子中stack[]并不是真正意义上的栈,“栈”在理论上应该只能访问顶端的元素,但那只是个形式问题),于是可以很容易地访问任何一步的点,输出的时候正着打反着打跳着打均可,程序中所有和predecessor有关的内容便可以删去了。

但是事实上这个办法在程序效率上是劣化而不是优化,首先虽然不需要predecessor了,但是栈空间消耗变得更大。原本栈空间的消耗和分岔路的多少有关,现在则是和路径的长度有关而与有多少岔路无关。那么栈空间的最小值应该是多大呢?私还没考虑好,但分配为整个迷宫的大小肯定是足够的。还有个问题是原来的方式由于覆盖了之前走过的路径,只保留岔路上其他方向的点,如果找到死路,弹栈后会直接跳到另外一个可能的岔路继续搜索,而修改后的方法如果找到死路,必须沿原路一步步跳回岔路口。再加上top++所用的时间,程序效率比原来要低,而且岔路越多越深入,效率上的差距越明显。

前几天看到个好玩的推,说“情人节我玩一天连连看,消灭一对是一对”。私寻思既然学了DFS和BFS,不如自己也写个文本连连看玩玩?再说吧。

另:为嘛我Tag里写C,wordpress会给自动补全成C++?