Service Unavailable
Service Unavailable
HTTP Error 503. The service is unavailable.貌似是微软的一个面试题：扫雷游戏，给出一个雷图，让求出每一个未知块是雷的概率。身为数学盲，概率论61分的菜鸟表示概率这东西没有任何想法，但是想了下确定某一块是雷还是非雷这点还是可以搞定的...
于是就YY了一道ACM题，输入一个合法雷图，要求标记其中一定为雷和一定不为雷的块
开始想暴力，暴力可以解决任何问题，但是太麻烦了，复杂度也高，完全搞不来
然后想网络流，网络流可以求出一个可行解，但貌似没有好的方法确定某一块（我只能想到枚举删除每个点的拆边），这完全是没有意义的
后来想到一个块只有两种状态，是雷和非雷，就想到前一段练过的2-sat了，也看到松鼠会里面一篇文章介绍扫雷逻辑，把扫雷转化为一个逻辑门电路的问题，然后说这是一个SAT问题，最后说这是一个NP问题。既然每个块只有两种状态，那就是2-SAT了，2-SAT可不是NP啊，或许我理解的有问题，不过貌似可以写代码了...
基本思想：
基本思想就是把一个逻辑关系用一条边来表示，从而将逻辑的传递关系转变成了图论中的连通问题，比如说：
如果事件A发生，则事件B肯定发生，就建边 A-&B
如果事件B发生，则事件C不能发生，就建边 B-&~C
这样建出的图就是 A-&B-&~C，那么我们就可以得到 A-&~C，即如果A发生，那么C不能发生
我们将一个事件的两种状态拆为两个点，然后按上面的逻辑关系建图，然后我们判断两个状态之间的连通性：
A-&~A，如果A发生了，那么A不能发生，说起来有点怪，换句话说就是A不能发生，如果A发生那么就会出现矛盾的逻辑关系
同样，如果~A-&A，则A肯定发生，如果两条边都有，那么有肯定这些逻辑关系中有矛盾，如果都没有边，那么就不能确定，两种情况都可以
从上面的分析来看，把一个未知块拆为两个点，一个表示该点为雷(x)，另一个表示非雷(~x)
然后枚举每个数字建边
0：0周围不会有雷的(x-&~x)，起始时不会出现0周围有块的情况，但之后会出现，下面会提到
1～8：如果数字n周围有k(k&=n)个未知块，那么只有两种情况可以判断：k=n时，全是雷，对每一个雷块建边 (~x-&x)；k=n+1，如果有一块不是雷，那么其他块全是雷，对每一个x块，令其他块为x'，则(~x-&x')
然后还可以想到数字1还有一些情况：对于1周围有大于1块时，如果某一块是雷，那么其他都不是雷 (x-&~x')
这样建好图，我们发现，我们人能判断的逻辑关系已经基本（后面还会说到一种情况）都加到图中了，然后重点到了：
对于一个点的两种状态，我们通过判断他们的连通情况来判断：
如果存在 x-&~x且~x-&x，也就是说存在矛盾，该情况不可能，我们保证是合法情况，不去考虑了
存在x-&~x但不存在~x-&x，说明某块不可能是雷
存在~x-&x但不存在x-&~x，说明某块肯定是雷
两个点不连通，好吧，这个块还不能确定
这样，就像人判扫雷一样，扫了一遍，但是我们发现，这样一次做过后并不能判断出全部的雷块和非雷块，对一些判断比较复杂的块还是可以确定他是雷非雷的，那么我们就多做几次好了，我们把前一次判断出来的雷和非雷加入新一轮的判断中，是雷的话就把周围数字减1，块数减1，非雷的话块数减1（这时候就会有0了），然后继续做，直到没有新的状态被确定为止，扫雷完成！！
(O不是雷，X是雷，#不确定)
下面代码：
1 #include&cstdio&
2 #include&cstring&
3 #include&cctype&
6 char maze[15][15];
7 int id[15][15],
8 int dir[8][2]={{-1,-1},{-1,0},{0,-1},{-1,1},{1,-1},{0,1},{1,0},{1,1}};
9 bool gra[100][100]; 10 int lx, 11
12 void floyd(int n){ 13
for(int k=0;k&n;k++){ 14
for(int i=0;i&n;i++){ 15
for(int j=0;j&n;j++){ 16
gra[i][j]|=gra[i][k]&gra[k][j]; 17
22 void build(){ 23
memset(gra,false,sizeof(gra)); 24
for(int i=0;i&(tid&&1);i++) gra[i][i]= 25
for(int ii=0;ii&ii++){ 26
for(int jj=0;jj&jj++){ 27
if(isdigit(maze[ii][jj])){ 28
int cnt=0,type=maze[ii][jj]-'0'; 29
int block[10]; 30
for(int kk=0;kk&8;kk++){ 31
int tx=ii+dir[kk][0]; 32
int ty=jj+dir[kk][1]; 33
if(tx&0||ty&0||tx&=lx||ty&=ly) 34
if(maze[tx][ty]=='X') type--; 35
if(maze[tx][ty]!='#') 36
block[cnt++]=id[tx][ty]; 37
if(type){ 39
if(cnt==type){ 40
for(int i=0;i&i++){ 41
gra[block[i]&&1|1][block[i]&&1]= 42
}else if(cnt-1==type){ 44
for(int i=0;i&i++){ 45
for(int j=0;j&j++){ 46
if(i==j) 47
gra[block[i]&&1|1][block[j]&&1]= 48
for(int i=0;i&i++){ 53
gra[block[i]&&1][block[0]&&1|1]= 54
if(type==1){ 57
for(int i=0;i&i++){ 58
for(int j=0;j&j++){ 59
if(i==j) 60
gra[block[i]&&1][block[j]&&1|1]= 61
70 int main(){ 71
freopen("ms.in","r",stdin); 72
freopen("ms.out","w",stdout); 73
int t,cas=0; 75
scanf("%d",&t); 76
while(t--){ 77
scanf("%d%d",&lx,&ly); 79
for(int i=0;i&i++){ 80
scanf("%s",maze[i]); 81
for(int j=0;j&j++){ 82
if(maze[i][j]=='#'){ 83
id[i][j]=tid++; 84
bool flag= 88
while(flag){ 89
build(); 91
floyd(tid&&1); 92
for(int i=0;i&i++){ 95
for(int j=0;j&j++){ 96
if(maze[i][j]=='#'){ 97
bool a=gra[id[i][j]&&1][id[i][j]&&1|1]; 98
bool b=gra[id[i][j]&&1|1][id[i][j]&&1]; 99
if(a&b){100
puts("~~");101
}else if(b){102
maze[i][j]='X';flag=103
}else if(a){104
maze[i][j]='O';flag=105
printf("Case %d:\n",++cas);112
for(int i=0;i&i++){113
puts(maze[i]);114
puts("");116
我代码比较挫的，大致算起来O(n^4)，不错，确实太大了，为了偷懒用了floyd判连通，这个地方可以改成做n次dfs，也就可以将O(n^3)的减到O(n^2)，O(n^3)的总复杂度还是可以接受，另外那个while(true)循环，理论说可能做n次，不过我实在构造不来这样的数据，那个循环最多也就做两三次的样子，所以这个方法还是比较理想的～～（n为未知块个数&2，程序能处理最多50个未知块的数据，可以把数组范围适量改大）&&
扫雷时候还有另外的一种情况的判断，那就是给出雷的个数，雷的个数在扫雷后期还是很有作用的，比如下面的雷图：
221 XX2 #X2
剩1个或是0个雷，还有一些更复杂的情况，都可以通过雷的个数来判断某些块中是否存在雷，这样的问题不能用上面的方法来搞定，但是用概率就简单多了，又转化成了求概率的问题...
经过上面的一通乱搞，与数字相关的未知块都扫的差不多了，当然还有，尤其是一排2和一排1的情况，不过在上面的基础上求概率应该就简单多了...
#3223# ######
#2112#######
本文地址：/ambition/archive//Mine-sweeping.html&
求解扫雷游戏中的概率问题 | 死理性派小组 | 果壳 科技有意思[]作者：hutia - 来源：果壳 - 发表时间：日扫雷是一个很常见的游戏,就不多介绍了。 假设在一个 n * n 的雷区里,有 m 个雷,所有的格子都没有点开,那么随意在任何一个格子里,有雷的概率应该是 m ...C语言编写扫雷游戏程序.jsp_百度文库&评分:4/5&5页 由C语言编写的扫雷游戏程序代码,由注解扫雷游戏(c语言版)已经编译运行确认了: #...中国维和军人创新扫雷 攻克外军无解任务-中新中国维和军人创新扫雷 攻克外军无解任务 日 10:19 来源:新华 参与互动(0) “钱学森创新拓展班”90%学员取得免试攻读硕士学位资格,...再牛也给俺跪了!Windows8镜像已遭破解扫雷不花一分钱_业界动态_游...求高手,怎么破解扫雷!拜托各位了 3Q_百度知道1个回答 - 提问时间: 日xyzzyshift 这是密码,当看到屏幕左上方有一个一个像素大的小点时,这个位置就是雷 采纳哦而今漫步从头越 iPhone 3.1.2固件越狱解锁扫雷 — 爱活 Evolife...iPhone 3.1.2固件越狱解锁扫雷下载USBview软件(解压缩密码:evolife),解压缩后双击运行,点击配置,勾选“自动刷新”和“配置描述”。然后在...亿万老婆买一送一480_亿万老婆买一送一480_算名_算卦阴阳宅风水 格杀无论自作解人不冷不热 豫剧罗成算卦狼奔鼠窜西服 怎样供奉貔貅供应量蹈矩践墨丘陵 儿童联系起来遁阴匿景难弟 来之不易陕北高斋学士冀中 旺财手链高楼什...解扫雷 - Amb@HDU_站开发_电脑学(Xue5)貌似是微软的一个面试题:扫雷游戏,给出一个雷图,让求出每一个未知块是雷的概率。身为数学盲,概率论61分的菜鸟表示概率这东西没有任何想法,但是想了下确定某一...扫雷破解_百度知道解扫雷 - Amb@HDU_站开发_电脑学(Xue5)貌似是微软的一个面试题:扫雷游戏,给出一个雷图,让求出每一个未知块是雷的概率。身为数学盲,概率论61分的菜鸟表示概率这东西没有任何想法,但是想了下确定某一...解扫雷 - Amb@HDU - 博客园 - 爱库 - ikeepu貌似是微软的一个面试题:扫雷游戏,给出一个雷图,让求出每一个未知块是雷的概率。身为数学盲,概率论61分的菜鸟表示概率这东西没有任何想法,但是想了下确定某一...无解扫雷。。求宇宙之主破解_吞噬星空吧_百度贴吧6条回复&-&发帖时间:&日迷恋扫雷,但是身边的朋友都不能理解_扫雷吧_百度贴吧8条回复&-&发帖时间:&日求帮忙破解这个扫雷啦!!!_绝世唐门吧_百度贴吧55条回复&-&发帖时间:&日Windows 的扫雷必定有解吗? | 问答 | 果壳 科技有意思老公下班就开始玩扫雷都扫了6个小时了!!我快抓狂了(第2页)_娱乐...66条回复&-&发帖时间:&日在帮忙解下扫雷,谢谢啦_百度知道扫雷破解器(很强大的) - 下载频道 - CSDN强大的扫雷破解器,可以立刻破解windows自带的扫雷游戏的雷,呵呵,不错哦... 强大的扫雷破解器,可以立刻破解windows自带的扫雷游戏的雷,呵呵,不错哦资源积分:1分 下载...怎么解_扫雷吧_百度贴吧8条回复&-&发帖时间:&日破解版扫雷-一键就获胜的扫雷游戏 - 下载频道 - CSDN扫雷本是Windows自带的一个游戏程序,最近无聊把它修改了以下,第一次单击就获胜,呵呵~~有点像外挂似的。标题也被我改了,改成Hacker,呵呵,破解应该属黑客的职业...扫雷解残局_百度知道3个回答 - 提问时间: 日红色是雷,绿色不是雷。能推理的都给你推了。寻找破解扫雷的方法和步骤?_百度知道3个回答 - 提问时间: 日第二 次回答可 计算,还有一招,点出的数字上左右两键同时按下,要两下哦【巧解扫雷】这个有解,过程很精彩,有兴趣试试看?_奥茨玛公主吧_...要成为扫雷高手,先练好逻辑吧 | 科学人 | 果壳 科技有意思扫雷是一个颇费心思的游戏,稍有闪失就得从头再来。你多半觉得必须要仔细对待每个可能是雷的方块。其实,许多地雷之间相互是有关联的!只要判断一次就足以确定。想...【求解】图片里有文件求解密_扫雷吧_百度贴吧3条回复&-&发帖时间:&日扫雷会无解吗?_百度知道什么新X方什么疯狂的XX都是浮云,《论程序员学好英语正确方法的... 尼马我第一次翻译的是扫雷的AI文章,讨论如何用AI解扫雷中的一些困难的局面,翻译之后,先不说我扫雷水平提高了,感觉自己英文水平在某个领域又有了新认识,并且可以...这图 有无解 我感觉无解_扫雷吧_百度贴吧9条回复&-&发帖时间:&日【游戏解说】扫雷—在线播放—优酷,视频高清在线观看【游戏解说】扫雷 玩得绝壁不如很多大大/小学生【?】技术渣,第一次撸视频求不嫌弃QWQ嫌弃也没办法QAQ简直要被自己蠢哭了QAQ求大神解析_扫雷吧_百度贴吧4条回复&-&发帖时间:&日解析国产扫雷装具:扫雷耙酷似猪八戒钉耙 【专家解读】该扫雷车配有爆破扫雷器、机械扫雷器和电子扫雷器三种,通过爆破、打碾、翻排、推压雷区土地等方法,提高扫雷速度,降低扫雷成本,减少触雷...谁能破解扫雷的联程序啊_使命召唤吧_百度贴吧5条回复&-&发帖时间:&日扫雷解答_百度知道6个回答 - 提问时间: 日接下来怎么点你会玩扫雷吗?&这基本是个没有开头也没有结尾的游戏，我们要做的就是无限地向下通关。据说在遥远的地心有一位美丽的公主在等待着我们，然而亦是据说，有人在PC版上用刺客刷到150多层都没有找到公主的下落。&游戏的巧妙之处在于将扫雷、RPG和策略类游戏结合在了一起。每一关都是6X5的未知格子空间，你需要逐格去探索，直到找到打开下一关的钥匙。你可能什么都没遇到，亦可能会开到怪物或宝箱，可能会遇到补给或金币，可能会遇到助手或机关。与此同时，你所选择的英雄亦在战斗和探索中不断成长或是受伤，获得装备或是魔法卡片，你需要仔细计算每场战斗的得失，才能以更好的状态坚持到最后。&游戏一共有四位英雄可供选择（新版本增加炼金术士），分别具有不同的初始属性和不同的天赋技能。其中后两位英雄需要在达到十层和二十层才能解锁拥有。具体的技能细节请参看下面的图文部分。需要提醒的是，在玩此游戏之前请先安装，否则游戏可能无法显示。&有兴趣的同学可以，下载PC、Mac、iOS、Andorid各种版本。&&&&英雄天赋介绍圣骑士：1.对不死族造成额外伤害；2.击杀不死族有一定几率增加攻击；3.重生后恢复生命百分比（仅限一次）；4.提升基础能力。吸血鬼：1.攻击非不死族怪物有一定几率恢复生命；2.攻击非不死族怪物有一定几率降低其攻击力，对不死族会造成小额度附加伤害；3.每一次攻击有一定几率对全体造成百分比伤害；4.提升基础能力。矮人：1.消耗道具回血时增加额外血量，并有一定几率提升攻击力；2.攻击有一定几率将敌人击晕3回合；3.攻击有一定几率附带额外伤害，伤害值取决于自身血量；4.提升基础能力。刺客：1.一定几率闪避攻击；2.一定几率触发两次攻击；3.敌人出现时立即消耗其百分比血量，并有一定几率将其定身一回合；4.提升基础能力。&道具介绍魔法类道具：1.绿鬼：三回合中毒；2.紫鬼：降低攻击；4.剑：先手攻击；5.铁拳：双倍攻击；6.熊玩具：将怪物转移到其他位置；7.羊仗：降低敌人血量并使其失去特殊属性；8.天雷：攻击全体；9.流星：对单体造成大量伤害；10.斗篷：隐身，使得怪物对周围方格的锁定失效；11.靴子：直接进入下一关。装备类道具：1.刀：增加攻击力；2.盔甲：降低怪物攻击力；3.戒指：进入下一关时恢复一定血量；4.油灯：显示陷阱位置；5.罗盘：显示关卡钥匙位置；6.地图：显示宝箱位置；7.红石：增加命中；8.蓝石：死后半血复活；9：幸运币：卖钱。&&另还有特殊怪物、特殊关卡和特殊商店待您自行探索~&&&------------------------ 作者寄语 ------------------------&我想谈点对这个游戏的感想和联想。&如果在电脑玩这款游戏，倒不如在手机上玩，想必那个界面是最适合手机的。&说起来，小时候一直喜欢的小浣熊水浒卡现在已经不见踪影，取而代之的是三国杀。&每个时代都有孩子们喜欢的游戏，或许那样的游戏在这些孩子长大之后，会消亡，变成记忆里的一张纸，随着时间流逝，变黄变脆，然后磨损在半空中，所能想起的，不过是些灰白的粉末罢了。&一如这款游戏，我们还都记得扫雷，那是每一台电脑里必备的游戏。与此共存的还有3D弹珠、红心大战、纸牌等游戏；我们也还都记得魔塔，现在好多攻略性游戏，我们都要不断去拯救公主，直到最后看到&从此两人过着幸福快乐的生活&，都还百看不厌。&于时代而言，童年很短；于个人而言，童年很长。&当年玩着变形金刚长大的一代，现如今看着电影版登上银幕，始终还是回到孩子的时候，尖叫，狂欢。&
微信扫描二维码分享
欢迎转载但请注明出处及链接，商业媒体使用请联系编辑（QQ ）。
10:27:32 发布 ┊ 35799 人浏览
你可能对以下文章感兴趣：&
<div id="review_contents_1层刺客，999血999攻，4回血戒指，每回合回血接近300（戒指会跟随关卡升级，刚开始很一般，后来很牛B），血低了就赶紧找到钥匙进入下一关，基本无敌，已自杀
不知道是不是我装的版本问题，居然有bug可以强制买点（弹出购买窗口的瞬间不会因为钱不够而变灰）。
话说，魔法道具介绍那里，怎么没有“3”呢？
这个游戏太作孽了，玩家简直是在自虐
<div id="review_contents_层炼金术士路过
RL类游戏？？支持！！！！
刺客+灯(防陷阱)无敌,谁用谁知道
<div id="review_contents_0层吸血鬼^^
手机上有&玩到后面没什么意思了
<div id="review_contents_0层&无聊刺客&路过&刺客加满技能表示很无敌&但是后期&无力&怪都上千学&60攻了&一层就要消耗200血&
怎么保存进度呀？？？
怎么安装安卓版？（顶锅盖溜走的小白冒死发问……）
求问PC版怎么进Shop？？找了半天都没找到。。。。不是开始界面的商店，是游戏过程中的商店。。。。。
商店是游戏过程中随机点出来的吧？回复：德雷克&求问PC版怎么进Shop？？找了半天都没找到。。。。不是开始界面的商店，是游戏过程中的商店。。。。。
囧，运气不佳。。。。我刚玩的时候以为下去了还可以上来。。。。。毕竟与魔塔还有区别。。。下不到12层的弱渣奋斗中。。。。。回复：单身农民&商店是游戏过程中随机点出来的吧？回复：德雷克&求问PC版怎么进Shop？？找了半天都没找到。。。。不是开始界面的商店，是游戏过程中的商店。。。。。
android版的我找到了，但是要收费，免费版只能玩圣骑和吸血鬼
android能找到免费，所有角色都开启版的回复：DevilX5&android版的我找到了，但是要收费，免费版只能玩圣骑和吸血鬼
<div id="review_contents_1层刺客，999血999攻，4回血戒指，每回合回血接近300（戒指会跟随关卡升级，刚开始很一般，后来很牛B），血低了就赶紧找到钥匙进入下一关，基本无敌，已自杀
没有人跟我一样觉得……电影版&Transformer&很丑？
四川省成都市锦江区
【每周镜像】系列作品作者，现在已经发展到开始写日记的地步鸟。
偷得浮生半日闲&
本站带宽由提供，特此鸣谢！
有意思吧版权所有标签 扫雷 | 问答 | 果壳网 科技有意思
如图则无解……
这里假设4左边的为A，右边的为B，2左面的为C，右面的为D,因为你还剩下两颗雷，所以只有两种可能性即：AD是雷，BC不是...
(C)2013果壳网&京ICP备号-2&京公网安备