Pagini recente » Cod sursa (job #2021678) | Cod sursa (job #1726688) | Cod sursa (job #690774) | Cod sursa (job #1097768) | Cod sursa (job #1609824)
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax = 550;
const double eps = 1e-3;
int n, m, N;
double a[Nmax][Nmax];
double D[23][23];
double x[Nmax];
inline int get(int x, int y) {
return x * (N + 1) + y;
}
void build() {
for (int i = 0; i <= get(N, N); i++) {
for (int j = 0; j <= get(N, N) + 1; j++) {
a[i][j] = 0;
}
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N - i; j++) {
if (i == 0 && j == N) {
a[get(i, j)][get(i, j)] = 1;
continue;
}
a[get(i, j)][get(i, j)] = -1;
if (j > 0)
a[get(i, j)][get(i, j - 1)] = 1. * j / N;
if (i > 0 && j < N)
a[get(i, j)][get(i - 1, j + 1)] = 1. * i / N;
if (i < N)
a[get(i, j)][get(i + 1, j)] = 1. * (N - i - j) / N;
a[get(i, j)][get(N, N) + 1] = -1;
}
}
}
void gauss() {
int i = get(0, 0), j = get(0, 0);
int n = get(N, N);
while (i <= n && j <= n) {
int k;
for (k = i; k <= n; k++) {
if (!(a[k][j] > -eps && a[k][j] < eps))
break;
}
if (k == n+1) {
j++;
continue;
}
if (k != i) {
for (int t = 0; t <= n + 1; t++) {
swap(a[i][t], a[k][t]);
}
}
for (int l = j + 1; l <= n + 1; l++) {
a[i][l] = a[i][l] / a[i][j];
}
a[i][j] = 1;
for (int lin = i + 1; lin <= n; lin++) {
for (int col = j + 1; col <= n + 1; col++) {
a[lin][col] -= a[lin][j] * a[i][col];
}
a[lin][j] = 0;
}
i++;
j++;
}
for (i = n; i >= 0; i--) {
for (j = 0; j <= n; j++) {
if (a[i][j] < -eps || a[i][j] > eps) {
break;
}
}
x[j] = a[i][n + 1];
for (int k = j + 1; k <= n; k++)
x[j] -= x[k] * a[i][k];
}
}
int main() {
freopen("minesweeper.in", "r", stdin);
freopen("minesweeper.out", "w", stdout);
scanf("%d %d", &n, &m);
N = n * m;
build();
gauss();
printf("%.6lf\n", x[get(0, 0)]);
return 0;
}