Pagini recente » Cod sursa (job #1172427) | Cod sursa (job #2504044) | Cod sursa (job #2089759) | Cod sursa (job #3136150) | Cod sursa (job #1788016)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin ("minesweeper.in"); ofstream fout ("minesweeper.out");
const int nmax = 23 * 23 + 10;
const double eps = 1e-8;
int n, nrst;
double ans[nmax + 1];
double a[nmax + 1][nmax + 1];
inline int indice (int i, int j) {
return i * (n + 1) + j;
}
void interschimba (int x, int y) {
for (int i = 0; i <= nrst + 1; ++ i) {
swap(a[ x ][ i ], a[ y ][ i ]);
}
}
void simplifica (int x, int y) {
double k = a[ x ][ y ];
for (int i = y; i <= nrst + 1; ++ i) {
a[ x ][ i ] /= k;
}
for (int i = x + 1; i <= nrst; ++ i) {
k = a[ i ][ y ];
for (int j = y; j <= nrst + 1; ++ j) {
a[ i ][ j ] -= a[ x ][ j ] * k;
}
}
}
void gauss() {
int j = 0;
for (int i = 0; i <= nrst; ++ i) {
int x;
while (j <= nrst) {
x = i;
while (x <= nrst && (-eps < a[ x ][ j ] && a[ x ][ j ] < eps)) {
++ x;
}
if (x <= nrst) {
break;
}
++ j;
}
if (j <= nrst) {
interschimba(i, x);
simplifica(i, j);
++ j;
}
}
for (int i = nrst; i >= 0; -- i) {
for (int j = 0; j <= nrst; ++ j) {
if (a[ i ][ j ] >= eps || a[ i ][ j ] <= -eps) {
ans[ j ] = a[ i ][nrst + 1];
for (int k = j + 1; k <= nrst; ++ k) {
ans[ j ] -= ans[ k ] * a[ i ][ k ];
}
break;
}
}
}
}
int main() {
int dn, dm;
fin >> dn >> dm;
n = dn * dm;
nrst = indice(n, n);
for (int i = 0; i <= n; ++ i) {
for (int j = 0; j <= n - i; ++ j) {
int k = indice(i, j);
a[ k ][ k ] = 1;
a[ k ][ indice(i - 1, j + 1) ] = -1.0 * i / n;
a[ k ][ indice(i, j - 1) ] = -1.0 * j / n;
a[ k ][ indice(i + 1, j) ] = -1.0 * (n - i - j) / n;
a[ k ][nrst + 1] = 1;
}
}
for (int i = 0; i <= nrst + 1; ++ i) {
a[ 0 ][ i ] = 0;
}
a[ 0 ][ 0 ] = 1;
gauss();
fout << setprecision( 10 ) << fixed;
fout << ans[ indice(n, 0) ] << "\n";
fin.close();
fout.close();
return 0;
}