Cod sursa(job #1882910)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 februarie 2017 16:31:45
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#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!