自动扫雷算法
发布时间: 2023-11-18 15:40:50
‘壹’ 扫雷公式及详解是什么
扫雷公式是一夹二，一有雷。二夹一，心有雷。二夹三，全有雷。 二二边，都有雷。三连一，中有雷。四连一，边有雷。
详解：
数字表示周围临近8个格子雷的数量，如此数字为2，则周围8个格子一共会有2个雷。
基础确定雷：基于上规则，若周围空地=数字，则空地均为【基础确定雷】。
等效：数字减去周围雷数为【等效数字】，如此3确定周围存有1雷，则等效为2。
等效在后续公式套用中会起到很关键的作用，基本来说，就是将一些不符合公式的情况，变为符合公式的情况。
一二一，边有雷：出现121列时，且2仅有一侧空地（3格），则如图，2的斜侧均为确定雷（并且2正侧方确定无雷）。由于“2122”的2周围有一个确定雷，则变化为“2121”形式，套用上公式。
二连一，边有雷：出现“a21b”时，a正侧为确定雷（并且b正侧确定无雷）。
一种等效变换的二连一：此情况中“314旗”，由于4侧有2雷，则4等效为2，变换为“312x”，套用上公式。
1221，二侧雷：出现“1221”时，2上确定雷。
二夹一，心有雷：在“x212x”时，1正侧方确定雷（并且1斜侧方确定无雷）。
如此情况，尽管无法确定雷的位置，但是可确定上方三格无雷。原理是由于雷一定出现在第二行，因此第二行的1已经被第二行满足，则上方无雷。而再推进一格，此时第2行的1被第三行满足，则1行2行均无雷 。
‘贰’ 请教扫雷算法
扫雷的算法有两种，一种是老手使用的（凭经验操作），一种是新手使用的，我现在介绍一下老手使用的算法：
1.点第一个空
2.若点开的是一个格，则继续第1步
若点开的是一片（打开数大于等于9），则进行第3步
3.观察一片格的边角，
若有一个格数字与它周围的空格数相等，在空格处标雷并在两侧格子上同时左右键双击
若没有这种情况则观察有无[经验公式]
这样做直到不能再找到为止（一般能完成初、中级或高级的50%了）进行第4步
4.检查边角，重复第1步
—————
注：
[经验公式]：121组合，雷在2上
1221组合，两个雷在2上
还有好多复杂的，得自己总结
至于扫雷图形成的算法，是根据你点开的第一个格在哪里，总之第一个雷总不能在那里。在点开后万分之几秒里形成雷图，一切都是随机的，不过有一点对于初级来说有十几万分之一的几率打开3BV=1的图，也就是说一下就开了。（3BV的意思是赢得这盘扫雷所需要的最少左键点击数，比如一大片的3BV就是1，而一个没在一大片的边缘的格的3BV也是1，）也就是说，打开一大片所形成的那些边缘的格都不算，3BV是目前评价难易程度的最好方法，这也是随机，初级在1~71，中级大概25~180，高级100~250
‘叁’ 扫雷点到空格时的算法 跪求
从手工点开的这个空格进行处理，按上右下左或你自己定义的一个顺序来判断相应位置的格式是否是空格且未被点开，如果不是，则跳过，如果是，则将其自动点开，同时把这几个位置加入队列后续处理。
简单的流程图示意：
当前位置是空白位置？----否--->非空白的处理
|
|是
|
V
加入队列
|
V
+--->队列为空？-------->是--->结束
||
||否
||
|V
|第一个元素出队
||
|V
|点开该元素所指的位置
||
|V
|上左下右的位置如果是空白且未点开则入队
||
--------+
上面是非递归的方案，递归方案则更容易了：
伪代码算法描述如下：
Click(pos)//点开pos这个位置
{
//IsClicked()判断是否是已经点开的格子
if(IsClicked(pos))
return;
//IsBlank()判断是否是空白格子
if(!IsBlank(pos))
{
点开非空白格子的处理
}
//下面是点开空白格子的处理
ClickBlank(pos);
}
ClickBlank(pos)
{
if(!IsBlank(pos))
rerurn;
if(IsClicked(pos))
return;
//下面对四个方向的格子进行自动点开
//你需要计算四向的格子位置，无效的直接返回
ClickBlank(pos上面的格子);
ClickBlank(pos右面的格子);
ClickBlank(pos下面的格子);
ClickBlank(pos左面的格子);
}
‘肆’ C语言扫雷算法，也可以别的语言，解释清楚算法就好
在这上面不好说明, 我有C的代码, 你看一下(DEVC++)
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
#definen15
intrestart=0;
intlast_sel_x,last_sel_y;
charin[20];
structPOINT
{
intx;
inty;
}pt;
//设置CMD窗口光标位置
voidsetxy(intx,inty)
{
COORDcoord={x,y};
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}
//获取当前CMD当前光标所在位置
voidgetxy()
{
HANDLEhConsole=GetStdHandle(STD_OUTPUT_HANDLE);
COORDcoordScreen={0,0};//光标位置
CONSOLE_SCREEN_BUFFER_INFOcsbi;
if(GetConsoleScreenBufferInfo(hConsole,&csbi))
{
//printf("光标坐标:(%d,%d) ",csbi.dwCursorPosition.X,csbi.dwCursorPosition.Y);
pt.x=csbi.dwCursorPosition.X;
pt.y=csbi.dwCursorPosition.Y;
}
}
structA
{
intvalue;//-1为雷
intstate;//显示状态:0为未打开,1为已打开
intlock;//锁定状态
intbomb;//雷已标记:0为未标记,1为已标记
};
structAs[10][10];
intcalc()
{
inti,j,count=0;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(s[i][j].state==0)count++;
}
}
returncount;
}
intprt()
{
system("cls");
intcount=calc();
inti,j;
printf("%3c",'');
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_GREEN);
for(i=0;i<10;i++)
{
printf("%3d",i);
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
for(i=0;i<10;i++)
{
printf(" ");
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_GREEN);
printf("%3d",i);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
for(j=0;j<10;j++)
{
if(s[i][j].bomb==1)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED);
printf("%3c",'*');
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
}
elseif(s[i][j].state==1)
{
if(s[i][j].value==0)printf("%3c",'');
elseprintf("%3d",s[i][j].value);
}
else
{
printf("%3c",'-');
}
/* if(s[i][j].value==-1) printf("%3c",'*');
elseprintf("%3d",s[i][j].value);*/
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_GREEN);
printf("%3d",i);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
}
printf(" ");
printf("%3c",'');
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_GREEN);
for(i=0;i<10;i++)
{
printf("%3d",i);
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
printf(" ");
getxy();
setxy(45,0);
printf("%d",count);
setxy(40,5);
printf("说明");
setxy(40,7);
printf("1:输入*xy(如:*55),则把第5行第5列");
setxy(40,8);
printf("标记为地雷");
setxy(40,10);
printf("2:输入xy(如55),则把第5行第5列打开");
if(count==n)
{
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(s[i][j].value==-1&&s[i][j].bomb==0)s[i][j].bomb=1;
if(s[i][j].value!=-1&&s[i][j].state==0)s[i][j].state=1;
}
}
setxy(50,2);
printf("success!");
setxy(pt.x,pt.y);
fflush(stdin);
getchar();
return1;
}
setxy(pt.x,pt.y);
return0;
}
voidspace_process(intx,inty)
{
inti,j;
if(x-1>=0&&y-1>=0)
{
if(s[x-1][y-1].value==0&&s[x-1][y-1].lock==0){s[x-1][y-1].state=1;s[x-1][y-1].lock=1;space_process(x-1,y-1);}
elseif(s[x-1][y-1].value!=-1)s[x-1][y-1].state=1;
}
if(x-1>=0)
{
if(s[x-1][y].value==0&&s[x-1][y].lock==0){s[x-1][y].state=1;s[x-1][y].lock=1;space_process(x-1,y);}
elseif(s[x-1][y].value!=-1)s[x-1][y].state=1;
}
if(x-1>=0&&y+1<10)
{
if(s[x-1][y+1].value==0&&s[x-1][y+1].lock==0){s[x-1][y+1].state=1;s[x-1][y+1].lock=1;space_process(x-1,y+1);}
elseif(s[x-1][y+1].value!=-1)s[x-1][y+1].state=1;
}
if(y-1>=0)
{
if(s[x][y-1].value==0&&s[x][y-1].lock==0){s[x][y-1].state=1;s[x][y-1].lock=1;space_process(x,y-1);}
elseif(s[x][y-1].value!=-1)s[x][y-1].state=1;
}
if(y+1<10)
{
if(s[x][y+1].value==0&&s[x][y+1].lock==0){s[x][y+1].state=1;s[x][y+1].lock=1;space_process(x,y+1);}
elseif(s[x][y+1].value!=-1)s[x][y+1].state=1;
}
if(x+1<10&&y-1>=0)
{
if(s[x+1][y-1].value==0&&s[x+1][y-1].lock==0){s[x+1][y-1].state=1;s[x+1][y-1].lock=1;space_process(x+1,y-1);}
elseif(s[x+1][y-1].value!=-1)s[x+1][y-1].state=1;
}
if(x+1<10)
{
if(s[x+1][y].value==0&&s[x+1][y].lock==0){s[x+1][y].state=1;s[x+1][y].lock=1;space_process(x+1,y);}
elseif(s[x+1][y].value!=-1)s[x+1][y].state=1;
}
if(x+1<10&&y+1<10)
{
if(s[x+1][y+1].value==0&&s[x+1][y+1].lock==0){s[x+1][y+1].state=1;s[x+1][y+1].lock=1;space_process(x+1,y+1);}
elseif(s[x+1][y+1].value!=-1)s[x+1][y+1].state=1;
}
}
intprocess_char(char*t,int*i,int*j)
{
intlen=strlen(t);
intx,y=0;
for(x=0;x<len;x++)
{
if(t[x]=='')
{
continue;
}
else
{
t[y++]=t[x];
}
}
t[y]=' ';
if(t[0]=='*')
{
*i=t[1]-'0';
*j=t[2]-'0';
if(s[*i][*j].bomb==1)
{
s[*i][*j].bomb=0;
s[*i][*j].state=0;
}
elseif(s[*i][*j].bomb==0&&s[*i][*j].state==0)
{
s[*i][*j].bomb=1;
}
return1;
}
elseif(t[0]>='0'&&t[0]<='9')
{
*i=t[0]-'0';
*j=t[1]-'0';
return0;
}
return1;
}
intplus(intx,inty)//返回0为出错，返回1为正确，返回-1为取消
{
intcount=s[x][y].value;
intbomb=0;
if(count==0||count==-1)return-1;
if(x-1>=0&&y-1>=0)
{
if(s[x-1][y-1].bomb==1)bomb++;
}
if(x-1>=0)
{
if(s[x-1][y].bomb==1)bomb++;
}
if(x-1>=0&&y+1<10)
{
if(s[x-1][y+1].bomb==1)bomb++;
}
if(y-1>=0)
{
if(s[x][y-1].bomb==1)bomb++;
}
if(y+1<10)
{
if(s[x][y+1].bomb==1)bomb++;
}
if(x+1<10&&y-1>=0)
{
if(s[x+1][y-1].bomb==1)bomb++;
}
if(x+1<10)
{
if(s[x+1][y].bomb==1)bomb++;
}
if(x+1<10&&y+1<10)
{
if(s[x+1][y+1].bomb==1)bomb++;
}
if(bomb==s[x][y].value)
{
if(x-1>=0&&y-1>=0)
{
if(s[x-1][y-1].value==-1&&s[x-1][y-1].bomb==0){return0;}
}
if(x-1>=0)
{
if(s[x-1][y].value==-1&&s[x-1][y].bomb==0)return0;
}
if(x-1>=0&&y+1<10)
{
if(s[x-1][y+1].value==-1&&s[x-1][y+1].bomb==0)return0;
}
if(y-1>=0)
{
if(s[x][y-1].value==-1&&s[x][y-1].bomb==0)return0;
}
if(y+1<10)
{
if(s[x][y+1].value==-1&&s[x][y+1].bomb==0)return0;
}
if(x+1<10&&y-1>=0)
{
if(s[x+1][y-1].value==-1&&s[x+1][y-1].bomb==0)return0;
}
if(x+1<10)
{
if(s[x+1][y].value==-1&&s[x+1][y].bomb==0)return0;
}
if(x+1<10&&y+1<10)
{
if(s[x+1][y+1].value==-1&&s[x+1][y+1].bomb==0)return0;
}
space_process(x,y);
inti,j;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
s[i][j].lock=0;
}
}
return1;
}
else
{
return-1;
}
}
voidprt_selected(intx,inty,intflag)
{
if(flag==0)
{
if(x>=0)x=last_sel_x;
if(y>=0)y=last_sel_y;
}
intplus=2;
getxy();
if(x>=0)
{
last_sel_x=x;
setxy(3,x+1);
intj;
if(flag==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_BLUE|FOREGROUND_INTENSITY);
elseSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
for(j=0;j<10;j++)
{
if(s[x][j].bomb==1)
{
if(flag==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|BACKGROUND_BLUE);
elseSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
printf("%3c",'*');
}
elseif(s[x][j].state==1)
{
if(s[x][j].value==0)printf("%3c",'');
elseprintf("%3d",s[x][j].value);
}
else
{
printf("%3c",'-');
}
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
}
if(y>=0)
{
inti;
last_sel_y=y;
for(i=0;i<10;i++)
{
if(last_sel_x==i) continue;
if(flag==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_BLUE|FOREGROUND_INTENSITY);
elseSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
setxy(3*y+3,i+1);
if(s[i][y].bomb==1)
{
if(flag==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|BACKGROUND_BLUE);
elseSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
printf("%3c",'*');
}
elseif(s[i][y].state==1)
{
if(s[i][y].value==0)printf("%3c",'');
elseprintf("%3d",s[i][y].value);
}
else
{
printf("%3c",'-');
}
}
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
setxy(pt.x,pt.y);
}
voidinput()//实时获取键盘输入
{
intc;
intx=-1,y=-1;
inti=0;
intfirst_num=0;
while(1)
{
fflush(stdin);
c=getch();
printf("%c",c);
if(c==10||c==13) break;
if(c==8&&i>0)
{
in[i-1]=' ';
if(in[0]=='*')
{
if(in[1]<'0'||in[1]>'9')
{
x=-1;
prt_selected(last_sel_x,-1,0);
}
if(in[2]<'0'||in[2]>'9')
{
y=-1;
prt_selected(-1,last_sel_y,0);
}
}
else
{
if(in[0]<'0'||in[0]>'9')
{
x=-1;
prt_selected(last_sel_x,-1,0);
}
if(in[1]<'0'||in[1]>'9')
{
y=-1;
prt_selected(-1,last_sel_y,0);
}
}
i--;
getxy();
setxy(pt.x,pt.y);
printf("");
setxy(pt.x,pt.y);
}
elseif(c=='*'||(c>='0'&&c<='9'))
{
in[i++]=c;
if(in[0]=='*')
{
if(in[1]!=' '&&in[1]>='0'&&in[1]<='9')
{
x=in[1]-'0';
}
else
{
x=-1;
}
if(in[2]!=' '&&in[2]>='0'&&in[2]<='9')
{
y=in[2]-'0';
}
else
{
y=-1;
}
}
elseif(in[0]>='0'&&in[0]<='9')
{
x=in[0]-'0';
if(in[1]>='0'&&in[1]<='9')
{
y=in[1]-'0';
}
else
{
y=-1;
}
}
elsex=-1;
if(x>-1)prt_selected(x,-1,1);
if(y>-1)prt_selected(-1,y,1);
}
}
}
intmain()
{
inti=0,j,x,y;
while(1)
{
restart=0;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
s[i][j].value=0;
s[i][j].state=0;
s[i][j].lock=0;
s[i][j].bomb=0;
}
}
srand((unsigned)time(0));
i=0;
while(i<n)
{
x=rand()%10;
y=rand()%10;
if(s[x][y].value!=-1)
{
s[x][y].value=-1;
i++;
}
}
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(s[i][j].value==-1) continue;
// n=0;
if(i-1>=0)
{
if(s[i-1][j].value==-1) s[i][j].value++;
if(j-1>=0)
{
if(s[i-1][j-1].value==-1) s[i][j].value++;
}
if(j+1<10)
{
if(s[i-1][j+1].value==-1) s[i][j].value++;
}
}
if(i+1<10)
{
if(s[i+1][j].value==-1) s[i][j].value++;
if(j-1>=0)
{
if(s[i+1][j-1].value==-1) s[i][j].value++;
}
if(j+1<10)
{
if(s[i+1][j+1].value==-1) s[i][j].value++;
}
}
if(j-1>=0)
{
if(s[i][j-1].value==-1) s[i][j].value++;
}
if(j+1<10)
{
if(s[i][j+1].value==-1) s[i][j].value++;
}
}
}
if(prt()==1)
{
restart=1;
continue;
}
while(1)
{
memset(in,' ',20);
fflush(stdin);
// scanf("%[^ ]",in);
input();
if(process_char(in,&i,&j)==1)
{
if(prt()==1)
{
restart=1;
break;
}
continue;
}
for(x=0;x<10;x++)
{
for(y=0;y<10;y++)
{
s[x][y].lock=0;
}
}
if(s[i][j].value==-1)
{
printf(" Bomb");
fflush(stdin);
getchar();
restart=1;
}
elseif(s[i][j].value==0)
{
s[i][j].state=1;
space_process(i,j);
}
elseif(s[i][j].state==1)
{
intre=plus(i,j);
{
switch(re)
{
case-1:
break;
case0:
printf(" Bomb");
fflush(stdin);
getchar();
restart=1;
break;
case1:break;
}
}
}
else
{
s[i][j].state=1;
}
if(prt()==1||restart==1)
{
restart=0;
break;
}
}
}
return0;
}
热点内容