Cod sursa(job #2309452)

Utilizator patcasrarespatcas rares danut patcasrares Data 29 decembrie 2018 00:14:49
Problema Minesweeper Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fin("minesweeper.in");
ofstream fout("minesweeper.out");
const double eps=1e-5;
int n,m,nr,a[35][35],k,poz;
double r[305][305],sol[305],f,g,val;
void elg()
{
    for(int j=1;j<=nr;j++)
        for(int i=j;i<=m;i++)
            if(abs(r[i][j])>eps)
            {
                for(int h=1;h<=nr+1;h++)
                    swap(r[j][h],r[i][h]);
                for(int h=j+1;h<=m;h++)
                    if(abs(r[h][j])>eps)
                    {
                        val=r[h][j]/r[j][j];
                        r[h][j]=0;
                        for(int c=j+1;c<=nr+1;c++)
                            r[h][c]-=val*r[j][c];
                    }
                    else
                        r[h][j]=0;
                break;
            }
            else
                r[i][j]=0;
    for(int i=m;i>0;i--)
    {
        poz=1;
        while(poz<=nr&&abs(r[i][poz])<=eps)
            poz++;
        if(poz==nr+1)
            continue;
        sol[i]=r[i][nr+1];
        for(int j=poz+1;j<=nr;j++)
            sol[i]-=sol[j]*r[i][j];
        sol[i]/=r[i][poz];
    }
}
int main()
{
    fin>>n>>m;
    n*=m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            a[i][j]=++nr;
    cout<<(nr+1);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            if(i<n)
            {
                k=a[i][j];
                r[k][k]=1;
                r[k][nr+1]=1;
                if(i>0)
                {
                    f=i;
                    f/=n;
                    r[k][a[i-1][j+1]]=-f;
                }
                if(j>0)
                {
                    f=j;
                    f/=n;
                    r[k][a[i][j-1]]=-f;
                }
                if(n-i-j>0)
                {
                    f=n-i-j;
                    f/=n;
                    r[k][a[i+1][j]]=-f;
                }
            }
    m=nr;
    elg();
    fout<<fixed<<setprecision(10)<<sol[n+1];
}