Pagini recente » Cod sursa (job #571012) | Cod sursa (job #995140) | Cod sursa (job #3172421) | Cod sursa (job #2357784) | Cod sursa (job #636334)
Cod sursa(job #636334)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int nmax = 25;
double C[2][nmax][nmax][nmax];
int Q[2][10000][3];
int pq[2], uq[2];
inline double fabs(double x)
{
if(x < 0)
return -x;
else return x;
}
int main()
{
freopen ("minesweeper.in", "r", stdin);
freopen ("minesweeper.out", "w", stdout);
int N, n, m, i, j, pas, x = 0, flag, a, b, c;
double Rez = 0, pondere = 0, last = -1, Tot = 0;
scanf("%d %d", &n, &m);
N = n * m;
C[0][N][0][0] = 1;
pas = 0;
Q[x][0][0] = 3;
while(1)
{
pas++;
while(pq[x] <= uq[x])
{
a = Q[x][pq[x]][0];
b = Q[x][pq[x]][1];
c = Q[x][pq[x]][2];
if(C[x][a][b][c])
{
if(a)
{
if(C[1 - x][a - 1][b + 1][c] == 0)
{
Q[1 - x][++uq[1 - x]][0] = a - 1;
Q[1 - x][uq[1 - x]][1] = b + 1;
Q[1 - x][uq[1 - x]][2] = c;
}
C[1 - x][a - 1][b + 1][c] += ((a * C[x][a][b][c]) / N);
}
if(b)
{
if(C[1 - x][a][b - 1][c + 1] == 0)
{
Q[1 - x][++uq[1 - x]][0] = a;
Q[1 - x][uq[1 - x]][1] = b - 1;
Q[1 - x][uq[1 - x]][2] = c + 1;
}
C[1 - x][a][b - 1][c + 1] += ((b * C[x][a][b][c]) / N);
}
if(c)
{
if(C[1 - x][a + 1][b][c - 1] == 0)
{
Q[1 - x][++uq[1 - x]][0] = a + 1;
Q[1 - x][uq[1 - x]][1] = b;
Q[1 - x][uq[1 - x]][2] = c - 1;
}
C[1 - x][a + 1][b][c - 1] += ((c * C[x][a][b][c]) / N);
}
}
pq[x]++;
}
if(C[1 - x][0][0][N])
{
Rez += pas * C[1 - x][0][0][N];
pondere += C[1 - x][0][0][N];
C[1 - x][0][0][N] = 0;
if(fabs(Tot - Rez/pondere) < 1e-10)
break;
Tot = Rez / pondere;
}
x = 1 - x;
memset(C[1 - x], 0, sizeof(C[1 - x]));
memset(Q[1 - x], 0, sizeof(Q[1 - x]));
pq[x] = 1;
uq[1 - x] = 0;
}
printf("%.6lf\n", Rez/pondere);
return 0;
}