Pagini recente » Cod sursa (job #694583) | Cod sursa (job #3221750) | Cod sursa (job #1724192) | Istoria paginii utilizator/edfgtrewq | Cod sursa (job #1703476)
#include <bits/stdc++.h>
#define maxN 25
#define e 0.0000000001
using namespace std;
int n, m, N, M, st[maxN][maxN];
double a[maxN * maxN][maxN * maxN], x[maxN * maxN];
void Swap(double &x, double &y)
{
double aux;
aux = x;
x = y;
y = aux;
}
void read()
{
freopen("minesweeper.in", "r", stdin);
scanf("%d %d", &n, &m);
n = n * m;
}
void Gauss()
{
int i = 0, j = 0;
while (i <= N && j <= M)
{
int x, y;
for (x = i; x <= N; ++ x)
if (a[x][j] < -e || a[x][j] > e)
break;
if (x == N + 1)
{
++ j;
continue;
}
if (x != i)
for (y = 0; y <= M + 1; ++ y)
Swap(a[x][y], a[i][y]);
for (y = j + 1; y <= M + 1; ++ y)
a[i][y] = (double)(a[i][y] / a[i][j]);
a[i][j] = 1.00000000000;
for (y = i + 1; y <= N; ++ y)
{
int c;
for (c = j + 1; c <= M + 1; ++ c)
a[y][c] -= a[y][j] * a[i][c];
a[y][j] = 0.0000000000;
}
++ i;
++ j;
}
}
void Coef()
{
int i, j, idx;
x[st[0][0]] = 0.00;
for (i = N; i >= 0; -- i)
for (j = 0; j <= M + 1; ++ j)
if (a[i][j] < -e || a[i][j] > e)
{
if (j == M + 1)
{
x[0] = 0;
return;
}
x[j] = a[i][M + 1];
for (idx = j + 1; idx <= M; ++ idx)
x[j] -= a[i][idx] * x[idx];
break;
}
}
void solve()
{
int i, j;
N = M = 0;
for (i = 0; i <= n; ++ i)
for (j = 0; i + j <= n; ++ j)
st[i][j] = N ++;
M = N;
for (i = 0; i <= n; ++ i)
for (j = 0; i + j <= n; ++ j)
{
int x = st[i][j], y;
if (x == 0)
{
a[x][x] = 1.000;
continue;
}
if (i > 0)
{
y = st[i - 1][j + 1];
a[x][y] = (double)(1.00 * i / n);
//a[x][N + 1] -= (double)(1.00 * i / n);
}
if (j > 0)
{
y = st[i][j - 1];
a[x][y] = (double)(1.00 * j / n);
//a[x][N + 1] -= (double)(1.00 * j / n);
}
if (n - j - i > 0)
{
y = st[i + 1][j];
a[x][y] = (double)(1.00 * (n - j - i) / n);
//a[x][N + 1] -= (double)(1.00 * (n - j - i) / n);
}
a[x][x] = -1.000;
a[x][N + 1] = -1.0000;
}
Gauss();
Coef();
}
void write()
{
freopen("minesweeper.out", "w", stdout);
printf("%.6lf", x[st[n][0]]);
}
int main()
{
read();
solve();
write();
return 0;
}