Pagini recente » Cod sursa (job #2586451) | Cod sursa (job #2087937) | Clasament qwerty-6 | Cod sursa (job #1084738) | Cod sursa (job #1882910)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
const int kMaxDim = 22*22 + 10;
const double kEps = 1e-7;
double eq[kMaxDim][kMaxDim], res[kMaxDim];
int whichState[kMaxDim][kMaxDim];
int main() {
std::ifstream inputFile("minesweeper.in");
std::ofstream outputFile("minesweeper.out");
int n, m;
inputFile >> n >> m;
n *= m;
//we will compute for each state (A, B, C) the expected number of steps
//to reach the final state (0, 0, N)
int stateCount = 0;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n - i; ++j)
whichState[i][j] = ++stateCount;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n - i; ++j) {
if (i == 0 && j == 0)
continue;
int state1 = (i > 0 ? whichState[i - 1][j + 1] : -1);
int state2 = (j > 0 ? whichState[i][j - 1] : -1);
int state3 = (i + j < n ? whichState[i + 1][j] : -1);
eq[ whichState[i][j] ][ whichState[i][j] ] = n;
if (state1 != -1)
eq[ whichState[i][j] ][state1] = -i;
if (state2 != -1)
eq[ whichState[i][j] ][state2] = -j;
if (state3 != -1)
eq[ whichState[i][j] ][state3] = -(n - i - j);
eq[ whichState[i][j] ][stateCount + 1] = n;
}
}
eq[1][1] = 1;
for (int i = 1, j = 1; i <= stateCount && j <= stateCount; ++i, ++j) {
bool found = false;
for (int k = i; k <= stateCount && !found; ++k) {
if (eq[k][j] > -kEps && eq[k][j] < kEps)
continue;
for (int l = 1; l <= stateCount + 1; ++l)
std::swap(eq[i][l], eq[k][l]);
found = true;
}
if (!found) {
--i;
continue;
}
for (int l = j + 1; l <= stateCount + 1; ++l)
eq[i][l] /= eq[i][j];
eq[i][j] = 1;
for (int k = i + 1; k <= stateCount; ++k) {
for (int l = j + 1; l <= stateCount + 1; ++l)
eq[k][l] -= eq[i][l] * eq[k][j];
eq[k][j] = 0;
}
}
for (int i = stateCount; i; --i) {
for (int j = 1; j <= stateCount; ++j) {
if (eq[i][j] > -kEps && eq[i][j] < kEps)
continue;
res[j] = eq[i][stateCount + 1];
for (int l = j + 1; l <= stateCount; ++l)
res[j] -= res[l] * eq[i][l];
res[j] /= eq[i][j];
break;
}
}
outputFile << std::setprecision(6) << std::fixed << res[ whichState[n][0] ] << '\n';
inputFile.close();
outputFile.close();
return 0;
}
//Trust me, I'm the Doctor!