Pagini recente » Cod sursa (job #3145462) | Cod sursa (job #2955988) | Cod sursa (job #2522588) | Cod sursa (job #2525404) | Cod sursa (job #639774)
Cod sursa(job #639774)
#include <stdio.h>
#include <algorithm>
#define f first
#define s second
#define NMAX 23
#define LMAX 305
using namespace std;
int n,m,A[NMAX][NMAX],r,stare_i;
pair <int,int> B[LMAX];
double C[LMAX][LMAX],rez[LMAX];
void code_entities()
{
int i,j;
for (i=0; i<=n; i++)
for (j=0; j<=n-i; j++)
{
A[i][j]=++r;
B[r].f=i; B[r].s=j;
if (i==n && j==0)
stare_i=r;
}
}
void make_recurrence()
{
int i,x,y;
C[1][1]=1;
for (i=2; i<=r; i++)
{
x=B[i].f; y=B[i].s;
if (x)
C[i][A[x-1][y+1]]=-(double)x/n;
if (y)
C[i][A[x][y-1]]=-(double)y/n;
if (n-x-y)
C[i][A[x+1][y]]=-(double)(n-x-y)/n;
C[i][i]=1; C[i][r+1]=1;
}
}
void do_gauss()
{
int i,j,k;
double fact;
for (i=1; i<=r; i++)
{
for (j=i+1; j<=r; j++)
{
fact=C[j][i]/C[i][i];
for (k=i; k<=r+1; k++)
C[j][k]-=C[i][k]*fact;
}
}
for (i=r; i>=1; i--)
{
rez[i]=C[i][r+1];
for (j=i+1; j<=r; j++)
rez[i]-=C[i][j]*rez[j];
rez[i]/=C[i][i];
}
}
int main()
{
freopen("minesweeper.in","r",stdin);
freopen("minesweeper.out","w",stdout);
scanf("%d%d",&n,&m);
n*=m;
code_entities();
make_recurrence();
do_gauss();
printf("%lf\n",rez[stare_i]);
return 0;
}