Cod sursa(job #1462959)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 19 iulie 2015 15:10:44
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define Nmax 500
#define eps 0.000000001

using namespace std;

int sum[Nmax],nr_var;
double a[Nmax][Nmax];

inline int Var(int x, int y)
{
    if(!x) return y+1;
    return sum[x-1]+y+1;
}

inline void SwapL(int l1, int l2)
{
    if(l1==l2) return;
    for(int i=1;i<=nr_var+1;++i) swap(a[l1][i],a[l2][i]);
}

int main()
{
    int n,m,i,j,k,var;
    ifstream cin("minesweeper.in");
    ofstream cout("minesweeper.out");
    cin>>n>>m;
    n*=m; nr_var=(n+1)*(n+2)/2;
    sum[0]=n+1;
    for(i=1;i<=n;++i) sum[i]=sum[i-1]+n-i+1;
    a[1][1]=1;
    for(i=0;i<=n;++i)
        for(j=0;j<=n-i;++j)
        {
            if(!i && !j) continue;
            int var=Var(i,j);
            a[var][var]=1;
            if(i)
                a[var][Var(i-1,j+1)]=(double)-i/n;
            if(j)
                a[var][Var(i,j-1)]=(double)-j/n;
            if(n-i-j)
                a[var][Var(i+1,j)]=(double)-(n-i-j)/n;
            a[var][nr_var+1]=1;
        }
    for(i=1;i<=nr_var;++i)
    {
        for(j=i;j<=nr_var && fabs(a[j][i])<=eps;++j);
        SwapL(i,j);
        for(j=1;j<=nr_var;++j)
            if(i!=j)
            {
                double rap=-(a[j][i]/a[i][i]);
                for(k=1;k<=nr_var+1;++k) a[j][k]+=rap*a[i][k];
            }
    }
    cout<<setprecision(10)<<fixed;
    cout<<(a[Var(n,0)][nr_var+1]/a[Var(n,0)][Var(n,0)])<<"\n";
    return 0;
}