Cod sursa(job #989808)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 26 august 2013 15:43:12
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const double eps = 0.000001;
int N, M;
int where[24][24], isnow;
double A[502][502], X[502];
int main()
{
ifstream fin("minesweeper.in");
ofstream fout("minesweeper.out");
fin >> N >> M;
N *= M;
for (int i = 0; i <= N; ++i)
for (int j = 0; i + j <= N; ++j)
where[i][j] = ++isnow;
for (int i = 0; i <= N; ++i)
for (int j = 0; i + j <= N; ++j)
{
A[where[i][j]][where[i][j]] -= 1.0;
int a = i, b = j, c = N - (a + b);
if (c == N) continue;
if (a != 0) A[where[i][j]][where[i - 1][j + 1]] += 1.0 * a / (a + b + c);
if (b != 0) A[where[i][j]][where[i][j - 1]] += 1.0 * b / (a + b + c);
if (c != 0) A[where[i][j]][where[i + 1][j]] += 1.0 * c / (a + b + c);
A[where[i][j]][isnow + 1] -= 1.0;
}
for (int i = 1, j = 1; i <= isnow && j <= isnow; ++i, ++j)
{
int findnow;
for (findnow = i; findnow <= isnow && !(A[findnow][j] < -eps || A[findnow][j] > eps); ++findnow);
if (findnow == isnow + 1)
{
--i;
continue;
}
for (int k = 1; k <= isnow + 1; ++k)
swap(A[i][k], A[findnow][k]);
double rednow = A[i][j];
for (int k = 1; k <= isnow + 1; ++k)
A[i][k] /= rednow;
for (int k = i + 1; k <= isnow; ++k)
{
rednow = A[k][j];
for (int l = 1; l <= isnow + 1; ++l)
A[k][l] -= A[i][l] * rednow;
}
}
for (int i = isnow; i >= 1; --i)
for (int j = 1; j <= isnow + 1; ++j)
if (A[i][j] < -eps || A[i][j] > eps)
{
X[j] = A[i][isnow + 1];
for (int k = i - 1; k >= 1; --k)
{
A[k][isnow + 1] -= X[j] * A[k][j];
A[k][j] = 0;
}
break;
}
fout << fixed << setprecision(8) << X[where[N][0]] << '\n';
fin.close();
fout.close();
}