扫雷及其简单解答(待续) - 湘生福地

简介：
C++文本模式下模拟经典的扫雷游戏，有简单的解答计算。

概要：
其中一处用到区域生长算法，其余的没有技术含量，纯属娱乐。

核心算法和数据结构：
见代码.

AI部分待续..

#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <vector>
#include <windows.h>

class CMyMine
{
public:
    CMyMine();
    ~CMyMine();
public:
    void Run();
    static int rand(void);
protected:
    void InitGame(void);
    void Show(void);
    void GetNeighbor(int pos,int* nb);
    bool CheckState();
public:
    void DeMark(int x ,int y,bool isC = false);
    void Mark(int x, int y,bool isC = false); //做标记
    void Mark(int pos,bool isC = false);
    void DeMark(int pos,bool isC = false);
    void WaitForInput();
    void Open(int x , int y); //打开
    void Open(int pos);
    int*  m_UserMark;
    int*  m_AIMark;
protected:
    void AI();
    enum  GAMESTATE {START,OVER,WIN,PAUSE};
    char      m_nHard;
    enum GAMESTATE   m_eGameState;
    int   m_nWidth;
    int   m_nHeight;
    int   m_nMineNum;
    bool  m_UsingAI;

    int*  m_CoreMap;
    int*  m_ViewMap;
    int   m_nGamep[12]; //游戏参数
    char* m_graphs[4];  //图像
};

CMyMine::CMyMine()
{
   //难度常数设置
    m_nGamep[0] = 10;
    m_nGamep[1] = 10;
    m_nGamep[2] = 10;
    m_nGamep[3] = 20;
    m_nGamep[4] = 15;
    m_nGamep[5] = 38;
    m_nGamep[6] = 30;
    m_nGamep[7] = 20;
    m_nGamep[8] = 100;
    m_nGamep[9] = 35;
    m_nGamep[10] = 25;
    m_nGamep[11] = 175;
    //图形符号
    m_graphs[0]     = "□"; //空
    m_graphs[1]     = "♀"; //炸弹
    m_graphs[2]    = "※"; //未打开
    m_graphs[3]     = "√"; //标记

    //??
    m_CoreMap = 0;
    m_ViewMap = 0;
    m_nHard   = '\0';
    m_nWidth  = 0;
    m_nHeight = 0;
    m_nMineNum= 0;
    m_UsingAI = false;
    m_eGameState = OVER;


}

CMyMine::~CMyMine()
{
    if(m_CoreMap)
    {
        delete[] m_CoreMap;
        m_CoreMap = 0;
    }
    if(m_ViewMap)
    {
        delete[] m_CoreMap;
        m_CoreMap = 0;
    }
}

void CMyMine::GetNeighbor(int pos, int* nb)
{
     nb[0] = pos - m_nWidth - 1;
     nb[1] = pos - m_nWidth;
     nb[2] = pos - m_nWidth + 1;
     nb[3] = pos - 1;
     nb[4] = pos + 1;
     nb[5] = pos + m_nWidth - 1;
     nb[6] = pos + m_nWidth;
     nb[7] = pos + m_nWidth + 1;

    if(pos == 0) //左上角
        nb[0] = nb[1] = nb[2] =nb[3] = nb[5] = -1;
    else if(pos == m_nWidth - 1)  //右上角
        nb[0] = nb[1] = nb[2] =nb[4] = nb[7] = -1;
    else if(pos == m_nWidth*(m_nHeight-1))  //左下角
        nb[0] = nb[3] = nb[5] =nb[6] = nb[7] = -1;
    else if(pos==m_nWidth*m_nHeight-1) //右下角
        nb[2] = nb[4] = nb[5] =nb[6] = nb[7] = -1;
    else if( pos < m_nWidth - 1  && pos > 0) //第一排
        nb[0] = nb[1] = nb[2] = -1;
    else if(pos > m_nWidth*(m_nHeight-1) && pos < m_nWidth*m_nHeight-1)//最后一排
        nb[6] =nb[7] = nb[8] = -1;
    else if(pos % m_nWidth == 0)
        nb[0] = nb[3] = nb[5] = -1;
    else if((pos+1)%m_nWidth == 0)
        nb[2] = nb[4] = nb[7] = -1;

}
int CMyMine::rand(void)
{
   static bool initlize = false;
   static int randint[1000];
   static int randIndex = 0;
   if(!initlize || randIndex > 999 )
   {
       initlize = true;
       srand((unsigned)time(NULL));
       for(int i = 0; i < 1000; i++)
           randint[i] = ::rand();
   }
   return randint[randIndex++];
}

void CMyMine::Run(void)
{
    using namespace std;
    while(true)
    {
        char inputkey = 'a';
        bool bExit = false;
        cout<<"welcome to text mine game!"<<endl;
        cout<<"please input a,b,c

. to select:"<<endl;
        cout<<"a,[start game]"<<endl;
        cout<<"b,[game info]"<<endl;
        cout<<"c,[exit]"<<endl;
        cin>>inputkey;
        switch(inputkey)
        {
            case 'a':
                {
                  //游戏状态控制:
                   InitGame();
                   while(!CheckState())
                   {
                       Show();
                       WaitForInput();
                   }
                   Show();
                   //bExit = true;
                   break;
                }
            case 'b':
                {
                    cout<<m_graphs[0]<<m_graphs[1]<<m_graphs[2]<<m_graphs[3]<<endl;
                    break;
                }
            case 'c':
                {
                    bExit = true;
                    break;
                }
            default:
            cout<<"input a,b,c to select!"<<endl<<endl<<endl<<endl;
            break;
        }
        if(bExit)
            break;
    }
}

void CMyMine::InitGame(void)
{
    using namespace std;
    do
    {
     cout<<"select diffculty:"<<endl;
     cout<<"a easy,b normal,c hard,d crazy

(a-d Only)"<<endl;
     cin>>this->m_nHard;
    }while(this->m_nHard<'a' && this->m_nHard >'d');
    m_nHard   = (m_nHard-'a')*3;
    m_nWidth  = m_nGamep[m_nHard];
    m_nHeight = m_nGamep[m_nHard+1];
    m_nMineNum = m_nGamep[m_nHard+2];
    //分配空间
    m_CoreMap  = new int[m_nWidth*m_nHeight];
    m_ViewMap  = new int[m_nWidth*m_nHeight];
    m_UserMark = new int[m_nWidth*m_nHeight];
    m_AIMark   = new int[m_nWidth*m_nHeight];
    int i=0,j=0;
    //生成地雷
    int k = 0;
    while(k<m_nMineNum)
    {
        //生成地雷
        int  pindex = this->rand()%(m_nWidth*m_nHeight);
        m_CoreMap[pindex]  = 9;
        for(i=0,k=0;i<m_nWidth*m_nHeight;i++)
            if(m_CoreMap[i]==9) k++;
    }
    for(i=0;i<m_nWidth*m_nHeight;i++)
    {//地图生成
        if(m_CoreMap[i] != 9)
            m_CoreMap[i]  =  0;
        m_ViewMap[i]  = -1;//未开采
        m_UserMark[i] =  0;//未标记
        m_AIMark[i]   =  0;//未标记
        int nb[8];
        int minenum = 0;
        GetNeighbor(i,nb);
        for(j=0;j<8;j++)
        {
            if(nb[j]<0 || nb[j]>= m_nWidth*m_nHeight)
                continue;
            if(m_CoreMap[nb[j]] == 9)
                minenum ++;
        }
        if(m_CoreMap[i]!=9)
            m_CoreMap[i]= minenum;
    }
    m_eGameState = START;
}

void CMyMine::Show(void)
{//如果已经显示
    using namespace std;
    int i=0,j=0;
    system("cls");
    if(m_eGameState == START)
    {

    for(i=0;i<=m_nHeight;i++)
        {
            if(i==0)
            {
                for(j=0;j<=m_nWidth;j++)
                {
                    if(j==0)
                    cout<<"  ";
                    else
                    {
                        if(j-1<10)
                            cout<<' ';
                        cout<<j-1;

                    }
                }
                cout<<endl;
                continue;
            }
            for(j=0;j<=m_nWidth;j++)
            {
                if(j==0)
                {
                    cout<<i-1;
                    if(i-1<10)
                        cout<<' ';
                    continue;
                }
                if(m_ViewMap[(i-1)*m_nWidth+(j-1)] == -1)
                {
                    if(m_UserMark[(i-1)*m_nWidth+(j-1)]==1 || m_AIMark[(i-1)*m_nWidth+(j-1)]==1)
                    {
                        cout<<m_graphs[3];
                    }
                    else
                        cout<<m_graphs[2];
                }
                else
                {
                   if(m_ViewMap[(i-1)*m_nWidth+(j-1)] == 0)
                   {
                       cout<<' '<<' ';
                   }
                   else
                   {
                        if(m_ViewMap[(i-1)*m_nWidth+(j-1)]>=0)
                        cout<<' ';
                        cout<<m_ViewMap[(i-1)*m_nWidth+(j-1)];
                   }
                }
            }// for j
            cout<<endl;
        }//for i
        cout<<'\n'<<endl;
    }
    else if(m_eGameState == OVER)
    {
        cout<<"Game Over!\n"<<endl;
    }//ifelse
    else if(m_eGameState == WIN)
    {
        cout<<"Congratulation!You Win!!\n"<<endl;
    }
}

bool  CMyMine::CheckState()
{
    if(m_eGameState == START)
    {
        bool bsucceed = true;
        for(int i=0;i<m_nWidth*m_nHeight;i++)
        {//地图生成
            if(m_CoreMap[i]!= 9 && m_ViewMap[i] == -1)
            {
                bsucceed = false;
                break;
            }
        }
        if(bsucceed)
            m_eGameState = WIN;
        return bsucceed;
    }
    return true;
}

void CMyMine::WaitForInput()
{
    using namespace std;
    while(true)
    {
        if(m_UsingAI)
        {
            AI();
            Sleep(1000);
            break;
        }
        char op = '0';
        int  x  = 0;
        int  y  = 0;
        cout<<"wait for your input,your choice: \n\"o x y\" to open the unware place,\n\"m x y\" to mark a mine \n\"d

x y\" delete a mark \n \"h\" to ask for Help \n \"a\" to using AI\n \"e\" to end game.."<<endl;
        cin>>op;
        if(op == 'o' || op == 'm')
            cin>>x>>y;
        if(op == 'o' || op == 'm' || op == 'd' ||op == 'h' ||op == 'e'||op == 'a')
        {
            if(!(x<0 ||x>m_nWidth || y<0 || y> m_nHeight))
            {
                switch(op)
                {
                    case 'o':
                        Open(x,y);
                        break;
                    case 'm':
                        Mark(x,y);
                        break;
                    case 'd':
                        DeMark(x,y);
                        break;
                    case 'h':
                        AI();
                        break;
                    case 'a':
                        m_UsingAI = true;
                        break;
                    case 'e':
                        m_eGameState = OVER;
                        break;
                    default:
                        break;
                }
                return;
            }
        }
    }
}

int main(void)
{
    CMyMine game;
    game.Run();
    return 0;
}

void CMyMine::Open(int pos)
{
    int y = pos/m_nWidth;
    int x = pos%m_nWidth;
    Open(x,y);
}

void CMyMine::Open(int x, int y)
{
    using namespace std;
    int j=0,i =0;
    int pid =0;
    if(m_ViewMap[y*m_nWidth+x] != -1)
        return;
    if(m_CoreMap[y*m_nWidth+x] == 9)
    {
        m_eGameState = OVER;
        return;
    }
    else if(m_CoreMap[y*m_nWidth+x] >0 && m_CoreMap[y*m_nWidth+x] < 9)
    {
        m_ViewMap[y*m_nWidth+x] = m_CoreMap[y*m_nWidth+x];
        return;
    }
    else if(m_CoreMap[y*m_nWidth+x] == 0)
    {//生长
        vector<int> barray;
        vector<int> tarray;
       barray.push_back(y*m_nWidth+x);
       pid = 0;
       while(pid <= barray.size())
       {
           int nb[8];
           int temp = barray[pid];
           GetNeighbor(temp,nb);
           pid = pid + 1;
           for(j=0;j<8;j++)
           {
               if(nb[j]<0 || nb[j] >= m_nWidth*m_nHeight)
                   continue;
               if(m_CoreMap[nb[j]] == 0)
               {//考虑nb[j] 是不是在barray内
                    bool isInbary = true;
                    for(i = 0;i< barray.size();i++)
                    {
                        if(barray[i] == nb[j])
                        {
                            isInbary = false;
                            break;
                        }
                    }
                    if(isInbary)
                    {
                        barray.push_back(nb[j]);
                    }
               }
               else if(m_CoreMap[nb[j]]>0 && m_CoreMap[nb[j]] < 9)
               {
                    bool isIntary = true;
                    for(i = 0;i<tarray.size();i++)
                        if(tarray[i] == nb[j])
                        {
                            isIntary = false;
                            break;
                        }
                        if(isIntary)
                        {
                            tarray.push_back(nb[j]);
                        }
               }
           }//for
       }//while
       for(i = 0;i<barray.size();i++)
       {
            m_ViewMap[barray[i]] = m_CoreMap[barray[i]];
       }
       for(i = 0;i<tarray.size();i++)
       {
            m_ViewMap[tarray[i]] = m_CoreMap[tarray[i]];
       }
    }//if
}

void CMyMine::Mark(int x, int y,bool isC)
{
    if(isC)
    {
        if(m_AIMark[y*m_nWidth+x] != 1)
            m_AIMark[y*m_nWidth+x] = 1;
    }
    else
    {
        if(m_UserMark[y*m_nWidth+x] != 1)
            m_UserMark[y*m_nWidth+x] = 1;
    }

}

void CMyMine::DeMark(int x, int y,bool isC)
{
    if(isC)
    {
        if(m_AIMark[y*m_nWidth+x] == 1)
            m_AIMark[y*m_nWidth+x] = 0;
    }
    else
    {
        if(m_UserMark[y*m_nWidth+x] == 1)
            m_UserMark[y*m_nWidth+x] = 0;
    }
}

void CMyMine::Mark(int pos,bool isC)
{
    if(isC)
    {
        if(m_AIMark[pos] != 1)
            m_AIMark[pos] = 1;
    }
    else
    {
        if(m_UserMark[pos] != 1)
            m_UserMark[pos] = 1;
    }
}

void CMyMine::DeMark(int pos,bool isC)
{
    if(isC)
    {
        if(m_AIMark[pos] == 1)
            m_AIMark[pos] = 0;
    }
    else
    {
        if(m_UserMark[pos] == 1)
            m_UserMark[pos] = 0;
    }
}

void CMyMine::AI()
{
    using namespace std;
    int i,j,k;
    //只提供ViewMap函数
    //状态参数
    int* lastView = NULL;
    int* lastMark = NULL;
    lastView = new int[m_nWidth*m_nHeight];
    lastMark = new int[m_nWidth*m_nHeight];
    memcpy(lastView,m_ViewMap,sizeof(int)*m_nWidth*m_nHeight);
    memcpy(lastMark,m_AIMark, sizeof(int)*m_nWidth*m_nHeight);

    vector<int> UnknowPointPos; //周围有未知点的安全已知点
    vector<int>    CurUMineNum;    //当前未知炸弹的个数
    vector<int>    UnknowPointSet;    //未知点点集格式为[size1 p11 p12 .. size2 p21 p22..]
    double* mP     = new double[m_nWidth*m_nHeight];//每一点更像mine的概率
    memset(mP,0,m_nWidth*m_nHeight*sizeof(double));  //初始化为0

    //计算整体概率[未知mine的数目/未知点的个数]
    double avgP = (double)m_nMineNum/(double)(m_nWidth*m_nHeight);//初始平均概率
    int       UnknownPoint = 0;
    int    UnknownMine  = 0;