自動掃雷演算法
發布時間: 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;
}
熱點內容