一个未知块是否有雷的概率该怎么计算？
通过前一片文章，我们可通过未知块周围已经确定的安全块给出的数字信息(不妨称这样的安全块为信息块)来确定此处是否还有雷.
当如下图这种情况时我们只需要某一个特定的信息块就能清楚的确定雷的所在。
如下图通过中心那个信息块能确定左下脚的那个未知块是有雷的。
这种情况往往在扫雷初级中很常见。
当然在一些情况下，我们无法通过未知块周围的一个信息块来判断此未知块是否有雷，但通过联合几个信息块却可以判断出其是否有雷。如下图：
上图第二排的第二块，单独看其周围的哪一个信息块都无法判断其是否有雷无雷，联合其右上脚的1，2信息块却可以很轻松的判断出它是一个安全块(无雷),想到了吧。把这个学会，你就可以去玩高级的扫雷了。
抽象为数学的观点，这就是计算一个联合概率问题。
把一个信息块周围关联的未知块组成一个集合，信息块的值减去信息块周围已经明确的雷块个数为集合的值。设未知块无雷时值为0，有雷时值为1。则集合的值为个未知块的值之和。计算未知块有雷的概率问题，转化为计算集合之间的联合概率。
抽象后的数学问题为：
已知元素a1,a2,...,an是可能为0或1的未知量，它们属于集合A1,A2,...,An. f(Ai)表示集合Ai的值，它为Ai集合中各元素之和，试确定其中一定为0或1的元素。
算法思想：
我们对元素a1,a2,...,an的各种组合建立一棵树，然后通过深度遍历来枚举每一种可能的情况，最后再计算各个元素为0或1的可能。
代码实现：
说明：
iData[11] = {2,2,3,3,1,2,3,3,4,5,6}; 实际上是三个集合，头一个数字表示集合的个数，后面紧跟为集合的元素的值，(实际上可用一个0或者负数来表示结尾)。
各个函数的意义：
DataApart 将iData中的数据分离。
CheckState 当前枚举状态是否满足各个集合的值.
#include <iostream>
#include <vector>
#include <algorithm>
namespace combination
{
void DataApart(int* iData,int nSetNum, std::vector<int>* &Sets)
{
using namespace std;
Sets = new vector<int>[nSetNum];
int i = 0;
bool bIsFull = true;
int nSetSize = 0;
int nIdx = 0;
while( i< nSetNum)
{
if(bIsFull)
{
nSetSize = iData[nIdx++];
bIsFull = false;
}
else
{
Sets[i].push_back(iData[nIdx++]);
if(Sets[i].size() == nSetSize)
{
bIsFull = true;
i++;
}
}
}
}
bool CheckState(int* iData,int* nFvalue,int nSetNum,std::vector<int> iUnionSet,std::vector<int> stack)
{
using namespace std;
bool bIsPass = true;
vector<int>* pfSets;
DataApart(iData,nSetNum,pfSets);
int i = 0,j = 0,k=0;
while(i<nSetNum)
{
int sum = 0, num = 0;
for(j = 0;j<pfSets[i].size();j++)
{
//在iUnionSet中找到pfSets[i][j]
for(k=0;k<stack.size();k++)
{
if(iUnionSet[k] == pfSets[i][j])
break;
}
if(k<stack.size())
{
sum += stack[k];
num += 1;
}
}
if(sum > nFvalue[i])
{
return false;
}
else if(nFvalue[i] - sum > pfSets[i].size() - num)
return false;
i++;
}
return true;
}
void Caculate(int* iData, int* nFvalue,std::vector<double>& fScore,int nSetNum)
{
using namespace std;
int i=0,j=0,k=0;
//分离数据
vector<int>* pfSets;
DataApart(iData,nSetNum,pfSets);
//计算并集
vector<int> iUnionSet;
i=0;
while(i<nSetNum)
{
for(j=0;j<pfSets[i].size();j++)
{
bool bIsIn = false;
for(k=0;k<iUnionSet.size();k++)
{
if(iUnionSet[k] == pfSets[i][j])
{
bIsIn = true;
break;
}
}
if(!bIsIn)
{
iUnionSet.push_back(pfSets[i][j]);
}
}
i++;
}
for(j = 0;j<iUnionSet.size();j++ )
{
cout<<iUnionSet[j]<<' ';
}
cout<<'\n';
sort(iUnionSet.begin(),iUnionSet.end());
for(j = 0;j<iUnionSet.size();j++ )
{
cout<<iUnionSet[j]<<' ';
}
cout<<'\n';
// 设置堆栈
int nStackSize = iUnionSet.size();
fScore.resize(nStackSize,0);
vector<int> stack;
vector<string> result;
//算法流程
stack.push_back(1);
//bool bIsStackEmp = false;
while(stack.size()>0)
{
if(CheckState(iData,nFvalue,nSetNum,iUnionSet,stack))
{
if(stack.size() < nStackSize)
stack.push_back(1);
else
{
//记录下此时的数据
string szTmp;
for(i=0;i<stack.size();i++)
{
if(stack[i] == 0)
{
szTmp+= string("0");
}
else
{
szTmp+= string("1");
}
}
result.push_back(szTmp);
//向上回溯
while(stack.back()==0)
{
if(stack.size()>1)
stack.pop_back();
else
break;
}
if(stack.back() == 1)
{
stack.pop_back();
stack.push_back(0);
}
else
{
stack.pop_back();
}
}
}
else
{//向上回溯
while(stack.back()==0)
{
if(stack.size()>1)
stack.pop_back();
else
break;
}
if(stack.back() == 1)
{
stack.pop_back();
stack.push_back(0);
}
else
{
stack.pop_back();
}
}
}
//统计结果
for(i=0;i<result.size();i++)
{
for(j=0;j<nStackSize;j++)
{
if(result[i][j] == '1')
{
fScore[j] += 1;
}
}
}
for(j=0;j<nStackSize;j++)
{
fScore[j] /= result.size();
}
}
}
int main(void)
{
int iData[11] = {2,2,3,3,1,2,3,3,4,5,6};
int nFValue[3] = {1,1,2};
std::vector<double> fScore;
combination::Caculate(iData,nFValue,fScore,3);
std::cout<<'\n';
for(int i=0;i<11;i++)
std::cout<<iData[i]<<' ';
std::cout<<std::endl;
for(i=0;i<fScore.size();i++)
std::cout<<fScore[i]<<' ';
return 0;
}