Cod sursa(job #1493139)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 28 septembrie 2015 19:22:41
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <vector>
#include <utility>
#include <iomanip>
using namespace std;

double solve_equations(vector<vector<double> >& mat, const int n){
	for(int i = 0; i < n; ++i){
		if(mat[i][i] == 0){
			int j = i+1;
			for( ; mat[j][i] == 0; ++j);
			swap(mat[i], mat[j]); }

		for(int j = i+1; j <= n; ++j){
			mat[i][j] /= mat[i][i]; }
		mat[i][i] = 1;
		for(int j = i+1; j < n; ++j){
			for(int k = i+1; k <= n; ++k){
				mat[j][k] -= mat[i][k] * mat[j][i]; }
			mat[j][i] = 0; } }
	return mat[n-1][n]; }

class encoder{
	vector<vector<int> > rez;
public:
	encoder(const int n): rez(n+1, vector<int>(n+1, 0)){
		for(int i = 0, x = 0; i <= n; ++i){
			for(int j = 0; i+j <= n; ++j){
				rez[i][j] = x++; } } }
	int operator()(const int a, const int b){
		return rez[a][b]; } };

double solve(const int n){
	encoder codifica(n);
	const int sz = codifica(n, 0)+1;
	vector<vector<double> > mat(sz, vector<double>(sz+1, 0));
	for(int nr_zero = 0; nr_zero <= n; ++nr_zero){
		for(int nr_unu = 0, nr_doi = n-nr_zero; nr_doi >= 0; ++nr_unu, --nr_doi){
			const int cod = codifica(nr_zero, nr_unu);
			mat[cod][cod] = mat[cod][sz] = n;
			if(nr_zero > 0){
				mat[cod][codifica(nr_zero-1, nr_unu+1)] -= nr_zero; }
			if(nr_unu > 0){
				mat[cod][codifica(nr_zero, nr_unu-1)] -= nr_unu; }
			if(nr_doi > 0){
				mat[cod][codifica(nr_zero+1, nr_unu)] -= nr_doi; } } }
	fill(begin(mat[0])+1, end(mat[0]), 0);
	mat[0][0] = 1;
	return solve_equations(mat, sz); }

int main(){
	ifstream f("minesweeper.in");
	ofstream g("minesweeper.out");
	int n, m;
	f >> n >> m;
	g << fixed << setprecision(6) << solve(n*m);
	return 0; }