扫雷－算法讨论

Cadina

wqx的内存情况~~~
用递归不好把

yoyohenry

发错版了~

TMZHJW

刚刚用yan的编译器编译，非常完美(+_+)！

Cloty

我的错位扫雷是用  用递归
为了加快速度，几乎胶尽脑汁。
最后做出来还比汇编的快些。

加快速度大概用了下面几种方法
预先算好格子
贴图简练
减少判断运算

诗诺比

我用的是a*算法的改版，自已优化过，速度很不错....
理论上比递归快，但占全局内存要大些

windybell

上面两位能否把代码贴出来看看呢?
我是初学者 ^_^

Cloty

lava版的很长，看不了的
最近写了个VS 的 算法基本相同，可以用VS的命令提示符 cl mine.c 编译
扫雷的算法其实也没什么好讨论的，只要最后结果行就行了

windybell

Thx~

JAY

对Cloty的Console美工无比崇拜~

windybell

附议～～

windybell

最近学C语言，拿Lava练手编了个扫雷．
不知道是递归快还是回溯快？
（本帖公布的代码供学习用，允许任何人转载．）

递归代码如下：

2. //=======================
3. //= 程序:挖地雷      =
4. //= 核心算法:递归     =
5. //= 作者:闫茂源      =
6. //= 地点:HB.JM.龙泉中学 =
7. //= 时间:2006/12/17    =
8. //=======================
9. #define FALSE 0
10. #define TURE 1
11. #define SMILE 1
12. #define OU 2
13. #define LAUGH 3
14. #define SAD 4
15. #define MARK 9
16. #define CROSS 10
17. #define BLACK 11
18. #define MINE 12
19. #define ENTER 13
20. #define KPD 14
21. #define KPU 19
22. #define KU 20
23. #define KD 21
24. #define KR 22
25. #define KL 23
26. #define KH 25
27. #define ESC 27
28. #define KF1 28
29. #define KSP 32
30. /*字符数据 0123456789*/
31. char number_0[]={0x3C,0x42,0x42,0x42,0x42,0x00,0x42,0x42,0x42,0x42,0x3C};
32. char number_1[]={0x00,0x02,0x02,0x02,0x02,0x00,0x02,0x02,0x02,0x02,0x00};
33. char number_2[]={0x3C,0x02,0x02,0x02,0x02,0x3C,0x40,0x40,0x40,0x40,0x3C};
34. char number_3[]={0x3C,0x02,0x02,0x02,0x02,0x3C,0x02,0x02,0x02,0x02,0x3C};
35. char number_4[]={0x00,0x42,0x42,0x42,0x42,0x3C,0x02,0x02,0x02,0x02,0x00};
36. char number_5[]={0x3C,0x40,0x40,0x40,0x40,0x3C,0x02,0x02,0x02,0x02,0x3C};
37. char number_6[]={0x3C,0x40,0x40,0x40,0x40,0x3C,0x42,0x42,0x42,0x42,0x3C};
38. char number_7[]={0x3C,0x02,0x02,0x02,0x02,0x00,0x02,0x02,0x02,0x02,0x00};
39. char number_8[]={0x3C,0x42,0x42,0x42,0x42,0x3C,0x42,0x42,0x42,0x42,0x3C};
40. char number_9[]={0x3C,0x42,0x42,0x42,0x42,0x3C,0x02,0x02,0x02,0x02,0x3C};
41. /*左侧表情数据*/
42. char face_smile[]={0x07,0xF0,0x08,0x08,0x10,0x04,0x20,0x02,0x20,0x02,0x40,0x01,0x4C,0x19,0x40,0x01,0x40,0x01,0x40,0x01,0x22,0x22,0x21,0xC2,0x10,0x04,0x08,0x08,0x07,0xF0,0x00,0x00};
43. char face_ou[]={0x07,0xF0,0x08,0x08,0x10,0x04,0x20,0x02,0x20,0x02,0x40,0x01,0x4C,0x19,0x4C,0x19,0x40,0x01,0x40,0x01,0x21,0xC2,0x22,0x22,0x11,0xC4,0x08,0x08,0x07,0xF0,0x00,0x00};
44. char face_laugh[]={0x07,0xF0,0x08,0x08,0x10,0x04,0x20,0x02,0x20,0x02,0x4F,0xF9,0x5F,0x7D,0x6E,0x3B,0x40,0x01,0x40,0x01,0x20,0x02,0x24,0x12,0x13,0xE4,0x08,0x08,0x07,0xF0,0x00,0x00};
45. char face_sad[]={0x07,0xF0,0x08,0x08,0x10,0x04,0x20,0x02,0x20,0x02,0x4A,0x29,0x44,0x11,0x4A,0x29,0x40,0x01,0x40,0x01,0x21,0xC2,0x22,0x22,0x10,0x04,0x08,0x08,0x07,0xF0,0x00,0x00};
46. /*雷区图形数据*/
47. char pic_blank[]={0xA8,0x50,0xA8,0x50,0xA8};
48. char pic_black[]={0xF8,0xF8,0xF8,0xF8,0xF8};
49. char pic_mine[]={0xA8,0x70,0xF8,0x70,0xA8};
50. char pic_mark[]={0x00,0x08,0x10,0xA0,0x40};
51. char pic_cross[]={0x88,0x50,0x20,0x50,0x88};
52. char pic_1[]={0x20,0x20,0x20,0x20,0x20};
53. char pic_2[]={0x70,0x10,0x70,0x40,0x70};
54. char pic_3[]={0x70,0x10,0x70,0x10,0x70};
55. char pic_4[]={0x50,0x50,0x70,0x10,0x10};
56. char pic_5[]={0x70,0x40,0x70,0x10,0x70};
57. char pic_6[]={0x70,0x40,0x70,0x50,0x70};
58. char pic_7[]={0x70,0x10,0x10,0x10,0x10};
59. char pic_8[]={0x70,0x50,0x70,0x50,0x70};
60. /*热线帮助数据*/
61. char HELP[]={"***** 热线帮助 *****====== 挖地雷 ======   --= 规则 =--   把所有没有地雷的方块挖开则胜；挖到地雷则失败；被挖开方块上的数字表示附近方块中地雷的数目。        --= 游戏界面 =--  分隔线右边是雷区，左上角显示游戏难度和剩余未标记的数目，左下角为时间。        --= 按键功能 =--  <><><><>移动光标<输入>挖开一个方块  <空格>标记一个方块  <> 连续挖开多个方块<F1>重新开局        --= 声明 =--   作者:Windy.Bell    日期:2006/12/16    QQ:115150813      = All rights left! ="};
62. /*声明全局变量*/
63. int Map[21][13];
64. int sum,mark;
65. /*把数字(8*11)写到缓存坐标 x,y 处*/
66. void ShowNumber(int x,int y,int n)
67. {
68.    if(n==0)WriteBlock(x,y,8,11,0,number_0);
69.    if(n==1)WriteBlock(x,y,8,11,0,number_1);
70.    if(n==2)WriteBlock(x,y,8,11,0,number_2);
71.    if(n==3)WriteBlock(x,y,8,11,0,number_3);
72.    if(n==4)WriteBlock(x,y,8,11,0,number_4);
73.    if(n==5)WriteBlock(x,y,8,11,0,number_5);
74.    if(n==6)WriteBlock(x,y,8,11,0,number_6);
75.    if(n==7)WriteBlock(x,y,8,11,0,number_7);
76.    if(n==8)WriteBlock(x,y,8,11,0,number_8);
77.    if(n==9)WriteBlock(x,y,8,11,0,number_9);
78. }
79. /*将表情(16*16)写到缓存坐标 8,32 处*/
80. void Face(int type)
81. {
82.    if(type==SMILE)WriteBlock(8,32,16,16,0,face_smile);
83.    if(type==OU)WriteBlock(8,32,16,16,0,face_ou);
84.    if(type==LAUGH)WriteBlock(8,32,16,16,0,face_laugh);
85.    if(type==SAD)WriteBlock(8,32,16,16,0,face_sad);
86. }
87. /*把图片(5*5)写到缓存*/
88. void ShowPic(int x,int y,int type)
89. {
90.    x=x*6+34;
91.    y=y*6+2;
92.    if(type==0)WriteBlock(x,y,5,5,0,pic_blank);
93.    if(type==1)WriteBlock(x,y,5,5,0,pic_1);
94.    if(type==2)WriteBlock(x,y,5,5,0,pic_2);
95.    if(type==3)WriteBlock(x,y,5,5,0,pic_3);
96.    if(type==4)WriteBlock(x,y,5,5,0,pic_4);
97.    if(type==5)WriteBlock(x,y,5,5,0,pic_5);
98.    if(type==6)WriteBlock(x,y,5,5,0,pic_6);
99.    if(type==7)WriteBlock(x,y,5,5,0,pic_7);
100.    if(type==8)WriteBlock(x,y,5,5,0,pic_8);
101.    if(type==MARK)WriteBlock(x,y,5,5,0,pic_mark);
102.    if(type==CROSS)WriteBlock(x,y,5,5,0,pic_cross);
103.    if(type==BLACK)WriteBlock(x,y,5,5,0,pic_black);
104.    if(type==MINE)WriteBlock(x,y,5,5,0,pic_mine);
105. }
106. /*清屏*/
107. void Cls()
108. {
109.    ClearScreen();
110.    Refresh();
111. }
112. /*将时间(24*11)写到左下侧(缓存 5,66)*/
113. void Timer(int time)
114. {
115.    int a,b,c;
116.    a=time/100;
117.    b=(time-a*100)/10;
118.    c=time-a*100-b*10;
119.    ShowNumber(5,66,a);
120.    ShowNumber(13,66,b);
121.    ShowNumber(21,66,c);
122. }
123. /*显示剩余地雷数*/
124. void MineNum(int i)
125. {
126.    int a;
127.    a=i/10;
128.    i=i-a*10;
129.    ShowNumber(16,17,a);
130.    ShowNumber(24,17,i);
131. }
132. /*查看帮助*/
133. void Help()
134. {
135.    int key,i;
136.    char temp[1600];
137.    GetBlock(0,0,160,80,0,temp);
138.    Cls();
139.    SetScreen(0);
140.    key=0;i=0;
141.    while(key!=ESC)
142.    {
143.       memcpy(_TEXT,HELP+i*20,100);
144.       UpdateLCD(0);
145.       key=getchar();
146.       if(key==KU)i--;
147.       if(key==KD)i++;
148.       if(key==KL)i=0;
149.       if(key==KR)i=19;
150.       if(key==KPU)i=i-5;
151.       if(key==KPD)i=i+5;
152.       if(i>19)i=19;
153.       if(i<0)i=0;
154.    }
155.    WriteBlock(0,0,160,80,0,temp);
156.    Refresh();
157. }
158. /*标记(x,y)处方块,已标记则撤消标记*/
159. void Mark(int x,int y)
160. {
161.    int i;
162.    i=Map[x][y];
163.    if(i<5)
164.    {
165.       if(i>1)
166.       {
167.         Map[x][y]=i-2;
168.         ShowPic(x,y,BLACK);
169.         mark--;
170.       }
171.       else
172.       {
173.         Map[x][y]=i+2;
174.         mark++;
175.         ShowPic(x,y,MARK);
176.       }
177.    }
178. }
179. [color=orangered]/*挖开方块(x,y),扫描(x,y)周围八个方块中的地雷数并显示*/
180. void Scan(int x,int y)
181. {
182.    int a,b,i,s;
183.    s=0;
184.    for(a=-1;a<2;a++)
185.    {
186.       for(b=-1;b<2;b++)
187.       {
188.         if(x+a>=0&&y+b>=0&&x+a<21&&y+b<13)
189.         {
190.            i=Map[x+a][y+b];
191.            if(i==1||i==3)s++;
192.         }
193.       }
194.    }
195.    sum++;
196.    ShowPic(x,y,s);
197.    Refresh();
198.    Map[x][y]=s+10;
199. }
200. /*从(x,y)处开始搜索可翻开的方块*/
201. void Sreach(int x,int y)
202. {
203.    int i;
204.    int tx,ty;
205.    int s[8],a[8],b[8];/*八个方向*/
206.    a[0]=-1;b[0]=-1;
207.    a[1]=-1;b[1]=0;
208.    a[2]=-1;b[2]=1;
209.    a[3]=0;b[3]=1;
210.    a[4]=1;b[4]=1;
211.    a[5]=1;b[5]=0;
212.    a[6]=1;b[6]=-1;
213.    a[7]=0;b[7]=-1;
214.    if(Map[x][y]==0)Scan(x,y);
215.    if(Map[x][y]==10)
216.    {
217.       Map[x][y]=19;
218.       for(i=0;i<8;i++)
219.       {
220.         tx=x+a[i];
221.         ty=y+b[i];
222.         if(tx>=0&&ty>=0&&tx<21&&ty<13)
223.         {
224.            if(Map[tx][ty]==0)Scan(tx,ty);
225.            if(Map[tx][ty]==10)Sreach(tx,ty);
226.         }
227.       }
228.    }
229. }[/color]/*连续翻开(x,y)周围的方块*/
230. int Around(int x,int y)
231. {
232.    int tx,ty;
233.    int a[8],b[8];
234.    int s[8],s1,s2,i;
235.    s1=0;s2=0;
236.    Face(OU);
237.    Refresh();
238. /*定义八个方向向量*/
239.    a[0]=-1;b[0]=-1;
240.    a[1]=-1;b[1]=0;
241.    a[2]=-1;b[2]=1;
242.    a[3]=0;b[3]=1;
243.    a[4]=1;b[4]=1;
244.    a[5]=1;b[5]=0;
245.    a[6]=1;b[6]=-1;
246.    a[7]=0;b[7]=-1;
247. /*扫描标记总数s1和错误标记数目s2*/
248.    for(i=0;i<8;i++)
249.    {
250.       tx=x+a[i];
251.       ty=y+b[i];
252.       if(tx>=0&&tx<21&&ty>=0&&ty<13)
253.       {
254.         s[i]=Map[tx][ty];
255.         if(s[i]==2||s[i]==3)s1++;
256.         if(s[i]==1)s2++;
257.       }
258.    }
259.    i=FALSE;/*返回值初始化*/
260. /*标记总数正确时连续翻开并改变返回值,否则直接返回FALSE*/
261.    if(s1==Map[x][y]-10)
262.    {
263.       for(i=0;i<8;i++)
264.       {
265.         tx=x+a[i];
266.         ty=y+b[i];
267.         if(tx>=0&&tx<21&&ty>=0&&ty<13)
268.         {
269.            if(s[i]==0)Sreach(tx,ty);
270.            if(s[i]==1)ShowPic(tx,ty,MINE);
271.         }
272.       }
273. /*有错误标记时返回TURE否则返回FALSE*/
274.       if(s2)i=TURE;
275.       else  i=FALSE;
276.    }
277.    Face(SMILE);
278.    Refresh();
279.    return i;
280. }
281. struct TIME
282. {
283.    int year;
284.    char month,day,hour,minute,second,week;
285. };
286. void main()
287. {
288.    int max;
289.    int x,y;
290.    int done,lost;
291.    int i,key;
292.    int t,h,m,s;
293.    struct TIME time;
294.    while(1)
295.    {
296. /*选择游戏难度*/
297.       i=5;
298.       key=0;
299.       Cls();
300.       Rectangle(56,36,104,44,2);
301.       Rectangle(50,20,110,47,1);
302.       Rectangle(51,48,110,49,1);
303.       Rectangle(111,21,112,49,1);
304.       TextOut(60,23,"难度:",0);
305.       while(key!=ENTER)
306.       {
307.         Rectangle(i*5+53,38,i*5+57,42,1);
308.         ShowNumber(92,23,i);
309.         key=0;
310.         Refresh();
311.         key=getchar();
312.         Rectangle(i*5+53,38,i*5+57,42,0);
313.         if(key==KR&&i<9)i++;
314.         if(key==KL&&i>1)i--;
315.         if(key==ESC)exit(0);
316.       }
317.       max=i*10;
318.       key=0;
319.       while(key!=ESC)
320.       {
321. /*开新局*/
322.         Cls();
323.         TextOut(44,32,"载入中...",0xc0);
324.         Box(40,28,120,51,0,1);
325.         Box(41,52,120,53,1,1);
326.         Box(121,29,122,53,1,1);
327. /*绘制游戏界面到缓冲区*/
328.         TextOut(2,2,"Lv ",0);
329.         TextOut(2,16,"剩",0);
330.         TextOut(4,50,"时间",0);
331.         ShowNumber(16,2,max/10);
332.         MineNum(max);
333.         Timer(0);
334.         Face(SMILE);
335.         Rectangle(4,64,29,78,1);
336.         Rectangle(32,1,32,79,1);
337.         Rectangle(0,0,159,0,1);
338. /*刷新雷区*/
339.         for(y=0;y<13;y++)
340.         {
341.            for(x=0;x<21;x++)
342.            {
343.               Map[x][y]=0;
344.               ShowPic(x,y,BLACK);
345.            }
346.         }
347. /*随机设置地雷位置*/
348.         x=rand()%21;
349.         y=rand()%13;
350.         for(i=0;i<max;i++)
351.         {
352.            while(Map[x][y])
353.            {
354.               x=rand()%21;
355.               y=rand()%13;
356.            }
357.         Map[x][y]=1;
358.         }
359.         Refresh();
360. /*初始化游戏参数*/
361.         x=0;y=0;
362.         mark=0;
363.         sum=0;
364.         done=FALSE;
365.         lost=FALSE;
366.         key=getchar();
367.         if(key==KH)Help();
368.         GetTime(time);
369.         h=time.hour;
370.         m=time.minute;
371.         s=time.second;
372. /*游戏控制部分*/
373.         while(key!=ESC&&key!=KF1&&lost==FALSE&done==FALSE)
374.         {
375.            GetTime(time);
376.            t=(time.hour-h)*3600+(time.minute-m)*60+(time.second-s);
377.            if(t>999)t=999;
378.            Timer(t);
379.            MineNum(max-mark);
380.            Refresh();
381.            Box(x*6+33,y*6+1,x*6+39,y*6+7,1,2);
382.            key=Inkey();
383.            if(key)
384.            {
385.               if(key==KR)
386.               {
387.                 x++;
388.                 Delay(100);
389.                 if(x>20)x=0;
390.               }
391.               if(key==KL)
392.               {
393.                 x--;
394.                 Delay(100);
395.                 if(x<0)x=20;
396.               }
397.               if(key==KU)
398.               {
399.                 y--;
400.                 Delay(100);
401.                 if(y<0)y=12;
402.               }
403.               if(key==KD)
404.               {
405.                 y++;
406.                 Delay(100);
407.                 if(y>12)y=0;
408.               }
409.               if(key==KH)
410.               {
411.                 Help();
412.                 Delay(500);
413.               }
414.               if(key==KSP)
415.               {
416.                 Mark(x,y);
417.                 Delay(200);
418.               }
419.               if(key==ENTER)
420.               {
421.                 Face(OU);
422.                 Refresh();
423.                 if(Map[x][y]==0)Sreach(x,y);
424.                 if(Map[x][y]==1)
425.                 {
426.                    lost=TURE;
427.                    ShowPic(x,y,MINE);
428.                 }
429.                 Face(SMILE);
430.                 Refresh();
431.               }
432.               if(key==KPU&&Map[x][y]>10)lost=Around(x,y);
433.            }
434.            if(sum==273-max)done=TURE;
435.            ReleaseKey(128);
436.         }
437. /*判断胜负，并显示地雷*/
438.         /*失败*/
439.         if(lost)
440.         {
441.            Face(OU);
442.            for(x=0;x<21;x++)
443.            {
444.               for(y=0;y<13;y++)
445.               {
446.                 if(Map[x][y]==1)ShowPic(x,y,MINE);
447.                 if(Map[x][y]==2)ShowPic(x,y,CROSS);
448.                 Refresh();
449.               }
450.            }
451.            Face(SAD);
452.            Refresh();
453.         }
454.         /*胜利*/
455.         if(done)
456.         {
457.            Face(OU);
458.            for(x=0;x<21;x++)
459.            {
460.               for(y=0;y<13;y++)
461.               {
462.                 if(Map[x][y]==1)ShowPic(x,y,MARK);
463.                 Refresh();
464.               }
465.            }
466.            Face(LAUGH);
467.            Refresh();
468.         }
469. /*若游戏因得出胜负而结束，则暂停在结束画面*/
470.         while(key!=ESC&&key!=KF1)
471.         {
472.            key=getchar();
473.            if(key==KH)
474.            {
475.               Help();
476.               Delay(500);
477.            }
478.         }
479.       }
480.    }
481. }
482. －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
483. 回溯如下：
484. /*从(x,y)处开始搜索可翻开的方块*/
485. void Sreach(int x,int y)
486. {
487.    int i;
488.    int step;/*步长*/
489.    int sa,sb,sc,sd,se,sf,sg,sh;/*八个方向*/
490.    int xx[273],yy[273];
491.    step=0;
492.    xx[step]=x;
493.    yy[step]=y;
494.    if(Map[x][y]==0)Scan(x,y);
495.    if(Map[x][y]==10)
496.    {
497.       L1:
498.       xx[step]=x;
499.       yy[step]=y;
500.       Map[x][y]=19;
501.       do
502.       {
503.         if(x>0&&y>0)
504.         {
505.            sa=Map[x-1][y-1];
506.            if(sa==0)
507.            {
508.               Scan(x-1,y-1);
509.               sa=Map[x-1][y-1];
510.            }
511.         }
512.         if(x>0)
513.         {
514.            sb=Map[x-1][y];
515.            if(sb==0)
516.            {
517.               Scan(x-1,y);
518.               sb=Map[x-1][y];
519.            }
520.         }
521.         if(x>0&&y<12)
522.         {
523.            sc=Map[x-1][y+1];
524.            if(sc==0)
525.            {
526.               Scan(x-1,y+1);
527.               sc=Map[x-1][y+1];
528.            }
529.         }
530.         if(y<12)
531.         {
532.            sd=Map[x][y+1];
533.            if(sd==0)
534.            {
535.               Scan(x,y+1);
536.               sd=Map[x][y+1];
537.            }
538.         }
539.         if(x<20&&y<12)
540.         {
541.            se=Map[x+1][y+1];
542.            if(se==0)
543.            {
544.               Scan(x+1,y+1);
545.               se=Map[x+1][y+1];
546.            }
547.         }
548.         if(x<20)
549.         {
550.            sf=Map[x+1][y];
551.            if(sf==0)
552.            {
553.               Scan(x+1,y);
554.               sf=Map[x+1][y];
555.            }
556.         }
557.         if(x<20&&y>0)
558.         {
559.            sg=Map[x+1][y-1];
560.            if(sg==0)
561.            {
562.               Scan(x+1,y-1);
563.               sg=Map[x+1][y-1];
564.            }
565.         }
566.         if(y>0)
567.         {
568.            sh=Map[x][y-1];
569.            if(sh==0)
570.            {
571.               Scan(x,y-1);
572.               sh=Map[x][y-1];
573.            }
574.         }
575.         if(x>0&&y>0&&sa==10)
576.         {
577.            x--;
578.            y--;
579.            step++;
580.            goto L1;
581.         }
582.         if(x>0&&sb==10)
583.         {
584.            x--;
585.            step++;
586.            goto L1;
587.         }
588.         if(x>0&&y<12&&sc==10)
589.         {
590.            x--;
591.            y++;
592.            step++;
593.            goto L1;
594.         }
595.         if(y<12&&sd==10)
596.         {
597.            y++;
598.            step++;
599.            goto L1;
600.         }
601.         if(x<20&&y<12&&se==10)
602.         {
603.            x++;
604.            y++;
605.            step++;
606.            goto L1;
607.         }
608.         if(x<20&&sf==10)
609.         {
610.            x++;
611.            step++;
612.            goto L1;
613.         }
614.         if(x<20&&y>0&&sg==10)
615.         {
616.            x++;
617.            y--;
618.            step++;
619.            goto L1;
620.         }
621.         if(y>0&&sh==10)
622.         {
623.            y--;
624.            step++;
625.            goto L1;
626.         }
627.         step--;
628.         x=xx[step];
629.         y=yy[step];
630.       }
631.       while (step>0);
632.    }
633. }

复制代码

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
我感觉是递归好些吧