Pagini recente » Cod sursa (job #816324) | Cod sursa (job #3163377) | Cod sursa (job #302188) | Cod sursa (job #2852188) | Cod sursa (job #1493139)
#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; }