Pagini recente » Cod sursa (job #2091268) | Monitorul de evaluare | Cod sursa (job #8614) | Cod sursa (job #1556914) | Cod sursa (job #1304734)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int Nmax = 25, Mmax = 300;
const double eps = 1e-10;
int Key[Nmax][Nmax];
double *A[Mmax], __A[Mmax][Mmax], X[Mmax];
void Gauss(int M, int N) {
for (int i = 1, j = 1; i <= N && j <= M; ++i, ++j) {
int k;
for (k = i; k <= N && abs(A[k][j]) < eps; ++k);
if (k == N + 1) {
--i;
continue;
}
if (i != k) swap(A[i], A[k]);
for (int k = j + 1; k <= M + 1; ++k)
A[i][k] /= A[i][j];
A[i][j] = 1;
for (int k = i + 1; k <= N; ++k) {
for (int p = j + 1; p <= M + 1; ++p)
A[k][p] -= A[i][p] * A[k][j];
A[k][j] = 0;
}
}
for (int i = N; i > 0; --i) {
for (int j = 1; j <= M + 1; ++j) {
if (abs(A[i][j]) > eps) {
X[j] = A[i][M + 1];
for (int k = j + 1; k <= M; ++k)
X[j] -= A[i][k] * X[k];
break;
}
}
}
}
int main()
{
ifstream fin("minesweeper.in");
ofstream fout("minesweeper.out");
int N, M;
fin >> N >> M;
N *= M;
int cnt = 0;
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N && i + j <= N; ++j)
Key[i][j] = ++cnt;
M = 0;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= N && i + j <= N; ++j) {
if (i == 0 && j == 0) continue;
++M;
A[M] = __A[M];
A[M][Key[i][j]] = 1;
if (i > 0)
A[M][Key[i - 1][j + 1]] = (double) -i / N;
if (j > 0 && (j - 1 != 0 || i != 0))
A[M][Key[i][j - 1]] = (double) -j / N;
if (N - i - j > 0)
A[M][Key[i + 1][j]] = (double) -(N - i - j) / N;
A[M][cnt + 1] = 1;
}
}
Gauss(cnt, M);
fout << setprecision(6) << fixed;
fout << X[Key[N][0]] << '\n';
fin.close();
fout.close();
}