Pagini recente » Cod sursa (job #3250117) | Cod sursa (job #105136) | Cod sursa (job #1301269) | Cod sursa (job #2776346) | Cod sursa (job #645069)
Cod sursa(job #645069)
#include <stdio.h>
#include <algorithm>
#define NMax 30
using namespace std;
const char IN[]="minesweeper.in",OUT[]="minesweeper.out";
int N,M,L,C,sol;
int T[NMax][NMax];
double v[NMax*NMax];
double Mat[NMax*NMax][NMax*NMax];
double rez[NMax*NMax];
void swapRow(int x,int y){
for (int i=1;i<=L+1;++i)
swap(Mat[x][i],Mat[y][i]);
}
void gauss()
{
int i,j,k,l;
for (i=1,j=1;i<=L;++i)
{
if (!Mat[i][j])
{
for (k=i+1;k<=L && !Mat[k][i];++k);
if (k<=L) swapRow(k,i);
}
for (l=i+1;l<=L;++l)
{
if (Mat[l][j]==0) continue;
double r=Mat[l][j]/Mat[i][j];
for (k=1;k<=L+1;++k)
Mat[l][k]-= Mat[i][k]*r;
}
++j;
}
for (i=L;i>0;--i)
{
rez[i]=Mat[i][L+1];
for (j=L;j>i;--j)
rez[i]-=Mat[i][j]*rez[j];
rez[i]/=Mat[i][i];
}
}
int main()
{
int i,j,c;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&M);
fclose(stdin);
N*=M;
for (i=0,c=0;i<=N;++i) for (j=0;i+j<=N;++j)
T[i][j]=++c;
L=c;
Mat[1][1]=1;
for (i=0;i<=N;++i)
for (j=(i==0);i+j<=N;++j)
{
if (i+j<N) Mat[T[i][j]][T[i+1][j]]= -(N-i-j)/(double)N;
if (i) Mat[T[i][j]][T[i-1][j+1]]= -i/(double)N ;
if (j) Mat[T[i][j]][T[i][j-1]]= -j/(double)N ;
Mat[T[i][j]][T[i][j]]=1;
Mat[T[i][j]][L+1]=1;
}
gauss();
freopen(OUT,"w",stdout);
printf("%lf\n",rez[L]);
fclose(stdout);
return 0;
}