Cod sursa(job #856720)

Utilizator stoicatheoFlirk Navok stoicatheo Data 16 ianuarie 2013 21:14:49
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <iostream>
#include <iomanip>
 
#define NLen 32
#define MLen 512
 
using namespace std;
 
int conf[NLen][NLen];
 
double E[MLen][MLen];
long double tm[MLen];
 
int main()
{
    freopen("minesweeper.in","r",stdin);
    freopen("minesweeper.out","w",stdout);
     
    int N,M;
     
    cin>>N>>M;
     
    N*=M;
    M=0;
     
    for(int i=0;i<=N;++i)
        for(int j=0;i+j<=N;++j)
            conf[i][j]=++M;
             
    ++M;
     
    for(int b=0;b<=N;++b)
        for(int c=0;b+c<=N;++c)
        {           
            int a=N-b-c;
             
            E[conf[b][c]][conf[b][c]]=1;
             
            if(c==N) continue;
             
            E[conf[b][c]][M]=1;
             
            if(a) E[conf[b][c]][conf[b+1][c]]-=(double)a/N;
             
            if(b) E[conf[b][c]][conf[b-1][c+1]]-=(double)b/N;
             
            if(c) E[conf[b][c]][conf[b][c-1]]-=(double)c/N;
        }
         
    for(int i=1;i<M;++i)
    {
        if(E[i][i]!=0)
        {
            for(int j=i+1;j<=M;++j) E[i][j]/=E[i][i];
            E[i][i]=1;
        }
         
        for(int k=i+1;k<M;++k)
            if(E[k][i]!=0)
            {
                for(int j=i+1;j<=M;++j) E[k][j]-=E[k][i]*E[i][j];
                E[k][i]=0;
            }
    }
 
    for(int i=M;i>0;--i)
    {
        tm[i]=E[i][M];
         
        for(int j=i+1;j<M;++j)
            tm[i]-=E[i][j]*tm[j];
    }
     
    cout<<fixed<<setprecision(6)<<tm[1]<<'\n';
         
    return 0;
}