Cod sursa(job #1225341)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 2 septembrie 2014 14:07:43
Problema Minesweeper Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <utility>

#define NMAX 235
#define eps 0.000001
using namespace std;

class sistem{
    inline void schimba(const int &i,const int &j){
        for(int k=1;k<=(n+1);k++)
            swap(mat[i][k],mat[j][k]);
    }

    inline void imp(const int &i,const double x){
        for(int k=1;k<=(n+1);k++)
            mat[i][k]/=x;
    }

    inline void scade(const int &i,const int &j,const double alfa){
        for(int k=1;k<=(n+1);k++)
            mat[i][k]-=(alfa*mat[j][k]);
    }

public:
    int n;

    double mat[NMAX][NMAX];
    double sol[NMAX];

    inline bool gauss(){
        int lin=0,i;

        for(int j=1;j<=n;j++){
            for(i=lin+1;i<=n;i++)
                if(fabs(mat[i][j])>=eps)
                    break;

            if(i==(n+1))
                continue;
            lin++;

            schimba(lin,i);

            imp(lin,mat[lin][j]);

            for(i=lin+1;i<=n;i++)
                scade(i,lin,mat[i][j]);
        }


        for(i=n;i>lin;i--)
            if(fabs(mat[i][n+1])>=eps)
                return 0;

        int j,k;
        for(i=lin;i>=1;i--){
            for(j=1;j<=n;j++)
                if(fabs(mat[i][j])>=eps)
                    break;

            sol[j]=mat[i][n+1];

            for(k=j+1;k<=n;k++)
                sol[j]-=(mat[i][k]*sol[k]);
        }

        return 1;
    }
}x;

map<pair<int,int>,int> toate;
int poz;

int variabila(int a,int b){
    if(!toate[make_pair(a,b)])
        toate[make_pair(a,b)]=++poz;
    return toate[make_pair(a,b)];
}

int main()
{
    ifstream cin("minesweeper.in");
    ofstream cout("minesweeper.out");

    int n=0,m=0;
    cin>>n>>m;

    n*=m;

    int j,k;
    int poz=0;

    x.n=((n+1)*(n+2))/2;

    variabila(n,0);
    x.mat[++poz][variabila(0,0)]=1;

    for(int i=0;i<=n;i++)
        for(j=0;j<=n-i;j++)
            if(i || j){
                k=n-i-j;

                x.mat[++poz][variabila(i,j)]=-1;

                if(i)
                    x.mat[poz][variabila(i-1,j+1)]=((double)i)/n;

                if(j)
                    x.mat[poz][variabila(i,j-1)]=((double)j)/n;

                if(k)
                    x.mat[poz][variabila(i+1,j)]=((double)k)/n;

                x.mat[poz][(n+1)*(n+2)/2+1]=-1;
            }

    if(!x.gauss())
        cout<<"No solution\n"; //Never happens
    else
        cout<<fixed<<setprecision(6)<<x.sol[1]<<'\n';

    cin.close();
    cout.close();
    return 0;
}