Cod sursa(job #1904316)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 5 martie 2017 14:23:47
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define Nmax 300
#define eps 0.000000000000000001

using namespace std;

int N,m,ind[30][30],n,wh[Nmax];
double a[Nmax][Nmax],ans[Nmax];

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

inline void Gauss()
{
    int i=1,j=1,k,t;
    int l=n;
    while(i<=l && j<=n)
    {
        for(k=i;k<=l && fabs(a[k][j])<eps;++k);
        if(k==l+1)
        {
            ++j; continue;
        }
        swapL(i,k);
        for(k=1;k<=l;++k)
        {
            if(k==i) continue;
            double r = -(a[k][j]/a[i][j]);
            for(t=1;t<=n+1;++t) a[k][t]+=r*a[i][t];
        }
        wh[i]=j;
        ++i; ++j;
    }
    for(i=1;i<=l;++i)
        if(wh[i]) ans[wh[i]] = a[i][n+1]/a[i][wh[i]];
}

inline bool ok(int x)
{
    return (x>=0 && x<=N);
}

int main()
{
    int i,j,p;
    double sum;
    ifstream cin("minesweeper.in");
    ofstream cout("minesweeper.out");
    cin>>N>>m; N*=m;

    for(i=0;i<=N;++i)
        for(j=0;j<=N-i;++j) ind[i][j]=++n;

    for(i=0;i<=N;++i)
        for(j=0;j<=N-i;++j)
        {
            if(!i && !j) continue;
            p=ind[i][j];
            a[p][p]=1;
            a[p][ind[i-1][j+1]]=-(double)i/N;
            a[p][ind[i][j-1]]=-(double)j/N;
            a[p][ind[i+1][j]]=-(double)(N-i-j)/N;
            a[p][n+1]=1;
        }
    a[ind[0][0]][ind[0][0]]=1;

    Gauss();
    cout<<setprecision(10)<<fixed<<ans[ind[N][0]]<<"\n";
    return 0;
}