#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int N, M;
long double SOL;
void gauss_swap_rows(int i, int j, int N, long double** A, long double* B, int* ID) {
if (i != j) {
int k;
long double tmp;
tmp = B[i];
B[i] = B[j];
B[j] = tmp;
ID[i] ^= ID[j];
ID[j] ^= ID[i];
ID[i] ^= ID[j];
for (k = i; k < N; ++k) {
tmp = A[i][k];
A[i][k] = A[j][k];
A[j][k] = tmp;
}
}
}
void gauss_swap_columns(int i, int j, int N, long double** A, long double* B, int* ID) {
if (i != j) {
int k;
long double tmp;
//ID[i] ^= ID[j];
//ID[j] ^= ID[i];
//ID[i] ^= ID[j];
for (k = 0; k < N; ++k) {
tmp = A[k][i];
A[k][i] = A[k][j];
A[k][j] = tmp;
}
}
}
void gauss_unswap(int N, long double *B, int *ID) {
int i;
long double* tmp = (long double*)(malloc(N * sizeof(long double)));
for (i = 0; i < N; ++i) {
tmp[ID[i]] = B[i];
}
for (i = 0; i < N; ++i) {
B[i] = tmp[i];
}
free(tmp);
}
void dump(int N, long double** A, long double* B) {
int i, j;
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
printf("%.2Lf ", A[i][j]);
}
printf("| %.2Lf\n", B[i]);
}
printf("----------------------------------------------------\n");
}
void gauss(int N, long double** A, long double* B) {
int i, j, k;
long double max;
int posA, posB;
double r;
//dump(N, A, B);
int* ID = (int*)(malloc(N * sizeof(int)));
for (i = 0; i < N; ++i) {
ID[i] = i;
}
for (i = 0; i < N; ++i) {
max = fabs(A[i][i]);
posA = i;
posB = i;
for (j = i; j < N; ++j) {
for (k = i; k < N; ++k) {
if (max < fabs(A[j][k])) {
max = fabs(A[j][k]);
posA = j;
posB = k;
}
}
}
gauss_swap_rows(i, posA, N, A, B, ID);
gauss_swap_columns(i, posB, N, A, B, ID);
//dump(N, A, B);
r = A[j][i] / A[i][i];
for (j = i + 1; j < N; ++j) {
B[j] -= r * B[i];
for(k = N; k >= i; --k) {
A[j][k] -= r * A[i][k];
}
}
B[i] /= A[i][i];
for(k = N; k >= i; --k) {
A[i][k] /= A[i][i];
}
}
for (i = N - 1; i >= 0; --i) {
for (j = i - 1; j >= 0; --j) {
B[j] -= (A[j][i] / A[i][i]) * B[i];
A[j][i] = 0;
}
}
//dump(N, A, B);
gauss_unswap(N, B, ID);
//dump(N, A, B);
free(ID);
}
long double** gauss_alloc_a(int N) {
int i, j;
long double** A;
A = (long double**)(malloc(N * sizeof(long double*)));
for (i = 0; i < N; ++i) {
A[i] = (long double*)(malloc(N * sizeof(long double)));
for (j = 0; j < N; ++j) {
A[i][j] = 0;
}
}
return A;
}
long double* gauss_alloc_b(int N) {
return (long double*)(malloc(N * sizeof(long double)));
}
int ID[23][23];
int main(void) {
int i, j, k;
FILE *f,*ff;
// citirea datelor
f = fopen("minesweeper.in", "r");
fscanf(f, "%d %d", &N, &M);
fclose(f);
// calcularea solutiei
N *= M;
int gaussN;
for (i = 0, gaussN = 0; i <= N; ++i) {
for (j = 0; i + j <= N; ++j, ++gaussN) {
ID[i][j] = gaussN;
}
}
long double** A1 = gauss_alloc_a(gaussN);
long double* B1 = gauss_alloc_b(gaussN);
for (i = 0, k = 0; i <= N; ++i) {
for (j = 0; i + j <= N; ++j, ++k) {
k = N - (i + j);
if (i + 1 <= N && j - 1 >= 0) {
A1[ID[i][j]][ID[i + 1][j - 1]] = -(long double)(i + 1) / N;
}
if (j + 1 <= N) {
A1[ID[i][j]][ID[i][j + 1]] = -(long double)(j + 1) / N;
}
if (i - 1 >= 0) {
A1[ID[i][j]][ID[i - 1][j]] = -(long double)(k + 1) / N;
}
A1[ID[i][j]][ID[0][0]] = 0;
A1[ID[i][j]][ID[i][j]] = 1;
}
}
B1[ID[N][0]] = 1;
gauss(gaussN, A1, B1);
B1[ID[0][0]] = 0;
long double** A2 = gauss_alloc_a(gaussN);
long double* B2 = gauss_alloc_b(gaussN);
for (i = 0, k = 0; i <= N; ++i) {
for (j = 0; i + j <= N; ++j, ++k) {
k = N - (i + j);
if (i + 1 <= N && j - 1 >= 0) {
A2[ID[i][j]][ID[i + 1][j - 1]] = -(long double)(i + 1) / N;
B2[ID[i][j]] += B1[ID[i + 1][j - 1]] * (long double)(i + 1) / N;
}
if (j + 1 <= N) {
A2[ID[i][j]][ID[i][j + 1]] = -(long double)(j + 1) / N;
B2[ID[i][j]] += B1[ID[i][j + 1]] * (long double)(j + 1) / N;
}
if (i - 1 >= 0) {
A2[ID[i][j]][ID[i - 1][j]] = -(long double)(k + 1) / N;
B2[ID[i][j]] += B1[ID[i - 1][j]] * (long double)(k + 1) / N;
}
A2[ID[i][j]][ID[0][0]] = 0;
A2[ID[i][j]][ID[i][j]] = 1;
}
}
gauss(gaussN, A2, B2);
// afisarea solutiei
ff = fopen("minesweeper.out", "w");
fprintf(ff, "%Lf\n", B2[ID[0][0]]);
fclose(ff);
return 0;
}