Cod sursa(job #633991)

Utilizator freak93Adrian Budau freak93 Data 15 noiembrie 2011 11:39:49
Problema Minesweeper Scor Ascuns
Compilator cpp Status done
Runda Marime 2.41 kb
#include <fstream>
#include <vector>
#include <string>
#define dd long double
using namespace std;

const char iname[] = "minesweeper.in";
const char oname[] = "minesweeper.out";

void build(int x, int a, int b, int c, vector< vector<dd> > &equations_matrix) {
	equations_matrix[x][x] = (a != -1) + (b != -1) + (c != -1);
	
	if (a != -1)
		equations_matrix[x][a] = -1;
	if (b != -1)
		equations_matrix[x][b] = -1;
	if (c != -1)
		equations_matrix[x][c] = -1;
	
	equations_matrix[x].back() = (a != -1) + (b != -1) + (c != -1);
}

/*
void display_matrix(vector< vector<double> > &matrix) {
	for (vector< vector<double> >::iterator it = matrix.begin(); it != matrix.end(); ++it) {
		for (vector<double>::iterator jt = it -> begin(); jt != it -> end(); ++jt)
			fprintf(stderr, "%.3lf ", *jt);
		fprintf(stderr, "\n");
	}
	fprintf(stderr, "\n");
}
*/

int main (int argc, char *argv[]) {
	//reading
	int N, M;
	string openfile = iname;
	if (argc > 1)
		openfile = argv[1];
	ifstream f(openfile.c_str());
	f >> N >> M;
	N *= M;
	f.close();

	//transforming every state (A, B, C) into a number
	int states = 0;
	vector< vector<int> > transform(N + 1, vector<int>(N + 1));

	for (int i = 0; i <= N; ++i)
		for (int j = 0; i + j <= N; ++j)
				transform[i][j] = states++;

	//building the matrix
	vector< vector<dd> > equations_matrix(states, vector<dd>(states + 1, 0));
	
	for (int i = 0; i <= N; ++i)
		for (int j = 0; i + j <= N; ++j) {
			if (i + j == 0)
				continue;

			int a = (i > 0 ? transform[i - 1][j + 1] : -1);
			int b = (j > 0 ? transform[i][j - 1] : -1);
			int c = (i + j < N ? transform[i + 1][j] : -1);
			int x = transform[i][j];

			equations_matrix[x][x] = N;
			if (a != -1)
				equations_matrix[x][a] = -i;
			if (b != -1)
				equations_matrix[x][b] = -j;
			if (c != -1)
				equations_matrix[x][c] = i + j - N;
			equations_matrix[x].back() = N;
		}
	
	equations_matrix[0][0] = 1;
	//display_matrix(equations_matrix);

	//gauss
	for (int i = 0; i < states; ++i)
		for (int j = 0; j < states; ++j)
			if (i != j)
				for (int k = states; k >= i; --k)
					equations_matrix[j][k] -= 
						equations_matrix[j][i] / equations_matrix[i][i] * 
							equations_matrix[i][k];
	
	//writing the output
	openfile.erase(openfile.size() -2, 2);
	openfile += "out";
	ofstream g(openfile.c_str());
	g.setf(ios::fixed, ios::floatfield);
	g.precision(6);
	g << equations_matrix[states - 1].back() / equations_matrix[states - 1][states - 1] << "\n";
	g.close();
}