hdu2262 Where is the canteen高斯+期待
hdu2262 Where is the canteen高斯+期望
Total Submission(s): 590 Accepted Submission(s): 148
Where is the canteen
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 590 Accepted Submission(s): 148
Problem Description
After a long drastic struggle with himself, LL decide to go for some snack at last. But when steping out of the dormitory, he found a serious problem : he can't remember where is the canteen... Even worse is the campus is very dark
at night. So, each time he move, he check front, back, left and right to see which of those four adjacent squares are free, and randomly walk to one of the free squares until landing on a canteen.
Input
Each case begin with two integers n and m ( n<=15,m<=15 ), which indicate the size of the campus. Then n line follow, each contain m characters to describe the map. There are 4 different type of area in the map:
'@' is the start location. There is exactly one in each case.
'#' is an impassible square.
'$' is a canteen. There may be more than one in the campus.
'.' is a free square.
'@' is the start location. There is exactly one in each case.
'#' is an impassible square.
'$' is a canteen. There may be more than one in the campus.
'.' is a free square.
Output
Output the expected number of moves required to reach a canteen, which accurate to 6 fractional digits. If it is impossible , output -1.
Sample Input
1 2 @$ 2 2 @. .$ 1 3 @#$
Sample Output
1.000000 4.000000 -1
Recommend
lcy
这题寻思了一段时间，一直没做，今天算是完成了。
可以参考这http://blog.csdn.net/acm_cxlove/article/details/7905778#comments
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL long long
using namespace std;
int n,m;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
char str[20][20];
double a[230][230];
bool flag[20][20];
int ans;
const double eps = 1e-12;
double x[230];
bool free_x[230];
int sgn(double x)
{
return (x>eps)-(x<-eps);
}
int gauss()
{
int i, j, k;
int max_r;
int col;
double temp;
int free_x_num;
int free_index;
int equ = n*m,var = n*m;
col = 0;
memset(free_x,true,sizeof(free_x));
for (k = 0; k < equ && col < var; k++, col++)
{
max_r = k;
for (i = k + 1; i < equ; i++)
{
if (sgn(fabs(a[i][col]) - fabs(a[max_r][col]))>0) max_r = i;
}
if (max_r != k)
{
for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
}
if (sgn(a[k][col]) == 0 )
{
k--; continue;
}
for (i = k + 1; i < equ; i++)
{
if (sgn(a[i][col])!=0)
{
double t = a[i][col] / a[k][col];
for (j = col; j < var + 1; j++)
{
a[i][j] = a[i][j] - a[k][j] * t;
}
}
}
}
for(i=k;i<equ;i++)
if(sgn(a[i][col])!=0) {return 0;}
if (k < var)
{
for (i = k - 1; i >= 0; i--)
{
free_x_num = 0;
for (j = 0; j < var; j++)
{
if ( sgn(a[i][j])!=0 && free_x[j]){
free_x_num++, free_index = j;
}
}
if(free_x_num>1) continue;
temp = a[i][var];
for (j = 0; j < var; j++)
{
if (sgn(a[i][j])!=0 && j != free_index) temp -= a[i][j] * x[j];
}
x[free_index] = temp / a[i][free_index];
free_x[free_index] = 0;
}
return var - k;
}
for (i = var - 1; i >= 0; i--)
{
temp = a[i][var];
for (j = i + 1; j < var; j++)
{
if (sgn(a[i][j])!=0) temp -= a[i][j] * x[j];
}
x[i] = temp / a[i][i];
}
return 1;
}
bool bfs()
{
int s,e;
memset(flag,false,sizeof(flag));
queue<int>x,y;
while(!x.empty()) x.pop();
while(!y.empty()) y.pop();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(str[i][j]=='$')
{
x.push(i);
y.push(j);
s=i;
e=j;
flag[i][j]=true;
}
while(!x.empty())
{
int ux=x.front(),uy=y.front(),vx,vy;
x.pop();y.pop();
for(int i=0;i<4;i++)
{
vx=ux+dir[i][0];
vy=uy+dir[i][1];
if(vx>=0&&vx<n&&vy>=0&&vy<m&&str[vx][vy]!='#'&&!flag[vx][vy])
{
flag[vx][vy]=true;
x.push(vx);y.push(vy);
}
}
}
return false;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%s",str[i]);
for(int i=0;i<=n*m;i++)
for(int j=0;j<=n*m;j++)
a[i][j]=0;
bfs();
int s,e;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int cnt=0;
if(str[i][j]=='@')
{
s=i;
e=j;
}
if(str[i][j]=='$')//目标的方程便是e[i]=0;
{
a[i*m+j][n*m]=0;
a[i*m+j][i*m+j]=1;
continue;
}
if(str[i][j]=='#') //不可达的点可以忽略
continue;
for(int k=0;k<4;k++)
{
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x>=0&&x<n&&y>=0&&y<m&&str[x][y]!='#'&&flag[x][y])
{
a[i*m+j][x*m+y]=1;
cnt++;
}
}
a[i*m+j][n*m]=-1*cnt;
a[i*m+j][i*m+j]=-1*cnt;
}
if(flag[s][e]&&gauss())
printf("%.6f\n",x[s*m+e]);
else
puts("-1");
}
return 0;
}