【技术交流】连连看 In JQuery 算法实现及源程序
前一阵子用JQuery做了一个连连看的程序自娱自乐，昨天有幸当上了技术交流版块的实习版主，自己应该努力把这一板块搞好，所以借此机会先献献丑，简单描述一下程序的实现过程，纯属雕虫小技，还望大家多多指正。众所周知，连连看程序最核心的算法是判断两张相同的图片是否可以连通，网上有很多算法，《编程之美》一书中也专门讨论过这个问题，下面的方法是我自己设计的，网上也没有搜索到相似的方式，虽然效率很一般，但是简单易懂、实现方便，希望各位多多指正。
上图中红色的图片是需要消去的图片，绿色部分是其中的某一条路径，该路径有三条折线，是最常见的情况，通过观察，这三条折线有这样的特点，如上图所示，其中有两条必然是和要消去的图片在一条直线上（图中蓝色部分），另外一条直线的两个端点必然是在上述两条直线上（图中绿色部分）
根据上面的观察，只要能构建这三条直线，那么这两张图片就可以连通。所以我的算法是这样的思路：
第一步:将需要消除的图片及其上下左右直到遇到其他图片之前的空白位置记录到一个数组中，如下图所示的紫色部分
可以看出，该数组中所有的点都和要消去的第一张图片在一条直线上。
第二步：以同样的方式将与之对应的图片存放到另外一个数组中，数组中所有的点和要消去的第二张图片在一条直线上
第三步：依次匹配这两个数组中的数据，如果他们在一条直线上而且中间没有其他图片，则说明第三条直线，也就是下图中绿色的部分可以连通，至此表示这两张图片联通，可以消去。
不难看出，这种方法对于两条折线和直线相连的图片同样适用
下面给出jQuery实现的关键部分：
1、用一个二维数组存放图片，实例中使用了34种图片，每种4个，下面的函数用于随机生成原始该数组
var get_arr = function(){
arr_zero();
k = 0;
for(i=1; i<=34; i++){
for(j=1; j<=4; j++){
ran_num = Math.floor(Math.random()*136);
while(che_blank_pos(ran_num)){
ran_num = Math.floor(Math.random()*136);
}
insert_to_array(ran_num,i);
}
}
}
var che_blank_pos = function(num){
num_raw = parseInt(num/17) + 1;
num_col = (num%17) + 1;
if(pic_arr != 0)
return true;
else
return false;
}
var insert_to_array = function(num, pic_num){
num_raw = parseInt(num/17) + 1;
num_col = (num%17) + 1;
pic_arr = pic_num;
};
var arr_zero = function(){
for(i=0; i<10; i++){
pic_arr = [];
for(j=0; j<19; j++){
pic_arr = 0;
}
};
}
2、将要消去的图片及其上下左右直到遇见其他图片的空白位置放置在数组中
match_one_insert = function(td_row, td_col){
match_array_one = [];
row = parseInt(td_row);
col = parseInt(td_col);
c = ;
match_array_one.push(c);
i_up = row-1;
while((i_up>=0) && (pic_arr==0)){
c = ;
match_array_one.push(c);
i_up--;
}
i_down = row+1;
while((i_down<10) && (pic_arr==0)){
c = ;
match_array_one.push(c);
i_down++;
};
i_left = col-1;
while((i_left>=0) && (pic_arr==0)){
c = ;
match_array_one.push(c);
i_left--;
};
i_right = col+1;
while((i_right<19) && (pic_arr==0)){
c = ;
match_array_one.push(c);
i_right++;
};
$('.first_click').removeClass('first_click');
$('.td_frame').addClass('first_click');
}
3、检测两张相同的图片是否能连通
var check_connect = function(){
for(i=0; i<match_array_one.length; i++){
for(j=0; j<match_array_two.length; j++){
one_row = match_array_one;
one_col = match_array_one;
two_row = match_array_two;
two_col = match_array_two;
if(one_row == two_row){
if(one_col == two_col)
return true;
else if(one_col > two_col){
p = two_col + 1;
while((pic_arr==0) && (p!=one_col)){
p++;
}
if(p == one_col)
return true;
}else{
p = one_col + 1;
while((pic_arr==0) && (p!=two_col)){
p++;
}
if(p == two_col)
return true;
}
}
if(one_col == two_col){
if(one_row == two_row)
return true;
else if(one_row > two_row){
p = two_row + 1;
while((pic_arr==0) && (p!=one_row)){
p++;
}
if(p == one_row)
return true;
}else{
p = one_row + 1;
while((pic_arr==0) && (p!=two_row)){
p++;
}
if(p == two_row)
return true;
}
}
};
}
return false;
}
4、点击图片触发相应函数，使用一个标志位识别是第几次点击图片
$('.mj_img').click(function(){
td_row = parseInt($(this).parent().attr('td_row'));
td_col = parseInt($(this).parent().attr('td_col'));
if(click_index == 0){
match_one_insert(td_row, td_col);
index_one_row = td_row;
index_one_col = td_col;
click_index = 1;
}else if(click_index == 1){
if((td_row==index_one_row) && (td_col==index_one_col)){
}else{
if(pic_arr == pic_arr){
match_two_insert(td_row, td_col);
if(check_connect()){
pic_arr = 0;
pic_arr = 0;
$('.td_frame').empty();
$('.td_frame').empty();
$('.first_click').removeClass('first_click');
}
}else{
match_one_insert(td_row, td_col);
index_one_row = td_row;
index_one_col = td_col;
}
}
}
});
}
我将该程序做成压缩包上传，有兴趣的同学可以玩一下。建议在chrome浏览器打开，IE下图片效果很不好，等找到更合适的图片再修改
哈哈哈 。。。 xywhere 发表于 2013-7-8 11:24
哈哈哈 。。。
不愧是抢沙发专家 很好，很强大啊！！！ 学习学习 这么高端的东西 {:5_136:} 话说这随机生成 是不是有可能出来无解的情况？ 小马 发表于 2013-7-8 11:26
很好，很强大啊！！！
这个不算你欠我的债啊 xywhere 发表于 2013-7-8 11:29
话说这随机生成 是不是有可能出来无解的情况？
这个是必然的。。。这个目前只关注图片是否可以连通，如果改进的话就要测试还有没有可以配对的了，如果没有了则自动刷新 话说大神……膜拜啊！！！{:5_153:} 前来膜拜大神 EagleFlag 发表于 2013-7-8 11:30
这个不算你欠我的债啊
算！！！ 这才像个技术版的像样的帖子嘛！ 不错 支持一下 虽然看不懂也要装b下 小分子的第一个神贴~~~~~~~~~顶！ 编程之美你都看完了？？？？？那还看什么“几株”！{:6_195:} 你的代码功力都练到这神级别了。。。。还用这么口爱的哆啦A梦，果然是你的风。。{:6_198:} 智商捉急。。。。。。。找了几对就眼花了{:6_190:}
下次换个阿狸版我来顶~~~~~~~{:10_432:} 膜拜下，挺厉害的说～ 阎魔あい 发表于 2013-7-8 11:41
话说大神……膜拜啊！！！
感谢支持啦，大神不敢当，勉强算是个初级业余程序员吧 lordboy 发表于 2013-7-8 11:51
前来膜拜大神
感谢支持，多多交流 小马 发表于 2013-7-8 12:13
算！！！
哼哼，战斗服还在我手上呢 admin 发表于 2013-7-8 12:17
这才像个技术版的像样的帖子嘛！
感谢洋哥的认可和支持 antty 发表于 2013-7-8 13:45
不错 支持一下 虽然看不懂也要装b下
感谢支持！多多交流 vo_ 发表于 2013-7-8 15:37
编程之美你都看完了？？？？？那还看什么“几株”！
我又不是神，哪儿能看完，走马观花翻了翻，你的爪哇学得怎么样了 vo_ 发表于 2013-7-8 15:36
小分子的第一个神贴~~~~~~~~~顶！
小圆总是这么贴心啊 vo_ 发表于 2013-7-8 15:41
你的代码功力都练到这神级别了。。。。还用这么口爱的哆啦A梦，果然是你的风。。
哆啦小圆~~~~ vo_ 发表于 2013-7-8 16:01
智商捉急。。。。。。。找了几对就眼花了
下次换个阿狸版我来顶~~~~~~~
我马上改进一下出个小圆特别版 terry 发表于 2013-7-8 18:25
膜拜下，挺厉害的说～
一般般啦，感谢晶晶同学的支持 EagleFlag 发表于 2013-7-8 19:59
感谢支持！多多交流
以后有大腿抱了{:5_134:} EagleFlag 发表于 2013-7-8 19:59
感谢洋哥的认可和支持
这是极好的技术贴！ 技术贴啊技术 EagleFlag 发表于 2013-7-8 19:58
哼哼，战斗服还在我手上呢
那不算了。。。。{:7_280:} EagleFlag 发表于 2013-7-8 20:01
我马上改进一下出个小圆特别版
期待ing 拼图也期待ing{:10_460:} EagleFlag 发表于 2013-7-8 20:00
我又不是神，哪儿能看完，走马观花翻了翻，你的爪哇学得怎么样了
离学成基础还有---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------这么长的距离{:8_361:} EagleFlag 发表于 2013-7-8 20:00
小圆总是这么贴心啊
辣必须的顶小分子是义不容辞的{:6_183:} 牛人啊，能原创的写出这么多东西真不错。。我也要好好学习了。。 这个问题其实可以简化为更新一个邻接矩阵的问题，每次用户点击两个图片，只需考虑M(p,q)是否等于1而且p，q两点是不是同一个图片id，判断两点联通简化为O（1）。
而每次成功的连连看，会带来最多不超过6列的状态更新，由于是三条边联通+1联通与否状态，正好4个bit即1int刚好可以表达完所有的状态。看起来状态更新最坏会有6n平方那么多，但是如果再引入图片是否存在的更新，操作数会更加少。整个算法只用申请一片空间，不需要push操作。
这个有点像低半处理的意思，快速判断联通，然后更新操作留在用户思考的时候完成。
EagleFlag 发表于 2013-7-8 19:58
感谢支持啦，大神不敢当，勉强算是个初级业余程序员吧
谦虚了啊。。。。。一向对于这种发技术贴的人怀着崇拜的心啊！！！！！{:5_153:} 去年面试创新工场的时候问过我这个题，我都不记得是怎么回答的了~~ 很长时间都没有看关于算法的了，顶一下 学习学习 这么高端的东西 .......................................... 学习学习嘛
页:
[1]