Pagini recente » Cod sursa (job #2657258) | Cod sursa (job #2090755) | Cod sursa (job #2636) | Cod sursa (job #2295785) | Cod sursa (job #1225341)
#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;
}