Cod sursa(job #1582231)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 27 ianuarie 2016 19:09:21
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("minesweeper.in");
ofstream g("minesweeper.out");
int N,M;
pair<int,int> V[25*25];
double A[405][405];
double X[405];
const double EPS = 0.00000001;
int Coresp[25][25],cnt;
void ReadAndPrecalc()
{
    f>>N>>M;
    N=N*M;
    M=N;
    for(int i=0;i<=N;i++)
        for(int j=0;i+j<=N;j++)
        {
            V[++cnt]=make_pair(i,j);
            Coresp[i][j]=cnt;
        }
}
void precalcA()
{
    for(int i=1;i<=cnt;i++)
    {
        int x=V[i].first,y=V[i].second;
        if(i==1)
        {
            A[i][i]=1;
            continue;
        }
        int number=0;
        double out=0;
        if(y>0)
        {
            ++number;
            A[i][Coresp[x+1][y-1]]=(double)y/(double)N;
        }
        if(x>0)
        {
            ++number;
            A[i][Coresp[x-1][y]]=(double)(x)/(double)N;
        }
        if(N-x-y>0)
        {
            ++number;
            A[i][Coresp[x][y+1]]=(double)(N-x-y)/(double)N;
        }
        A[i][i]=-1;
        A[i][cnt+1]=-1;
    }
}

void Solve()
{
    int i=1,j=1;
    N=M=cnt;
    while(i<=N&&j<=M)
        {
            int k;
            for(k=i;(A[k][j]<EPS&&A[k][j]>-EPS)&&k<=N;k++);
            if(k==N+1)
            {
                j++;
                continue;
            }
            if(k!=i)
                swap(A[i],A[k]);

            for(int l=j+1;l<=M+1;l++)
                A[i][l]/=A[i][j];
            A[i][j]=1;
            for(k=i+1;k<=N;k++)
                {
                    for(int l=j+1;l<=M+1;l++)
                        A[k][l]-=A[i][l]*A[k][j];
                    A[k][j]=0;
                }
        ++i;++j;
        }
    double S=0;
    for(i=N;i>=1;i--)
        {
            S=0;
            for(j=1;j<=M+1;j++)
                if(A[i][j]>EPS || A[i][j]<-EPS)
                    break;
            for(int k=j+1;k<=M;k++)
                S+=A[i][k]*X[k];
            X[i]=(A[i][M+1]-S)/A[i][i];
        }

}
int main()
{
    ReadAndPrecalc();
    int ind=Coresp[0][N];
    precalcA();
    Solve();
    g<<fixed<<setprecision(6)<<X[ind]<<"\n";
    return 0;
}