[ICPC2014 WF] Pachinko

题面翻译

题目描述

有一个宽度为 \(w\) 高度为 \(h\) 的方格纸， $ w \times h$ 的格子中，有一些是空的，有一些是洞，有一些是障碍物。从第一行的空的格子中随机选一个放置一个球，向上下左右移动的概率比为 \(p_u : p_d : p_l : p_r\) （满足 \(p_u + p_d + p_l + p_r = 100\)），不能移动到有障碍物的格子上。对于每个洞，输出落入该洞的概率。 \(w \le 20; h \le 10000\) 。保证第一行没有洞。

输入格式

第一行两个整数表示 \(w, h\) 。

第二行四个整数表示 \(p_u, p_d, p_l, p_r\) 。

接下来有一个 \(h\) 行 \(w\) 的字符矩阵，其中 . 表示空，X 表示障碍物，T 表示洞。

输出格式

若干行，每一行一个整数，按照矩阵从上到下，从左到右的顺序，输出每个洞的答案。绝对误差不超过 \(10 ^ -6\) 即为正确。

题目描述

You have been hired by Addictive Coin Machines to help design the next hit in their line of eye-catching, coin-guzzling, just-one-more-try Pachinko machines for casinos around the world.

Playing a Pachinko machine involves launching balls into a rectangular grid filled with pegs, obstacles, and targets. The ball bounces around the grid until it eventually hits one of the targets. The player earns a certain number of points depending on which target is hit.

The grid pattern for the next Pachinko machine has already been designed, but point values for the targets have not been assigned. These must be set so that like all casino machines, the machine is profitable but not too profitable. Thus it is important to figure out the probability of a ball hitting any particular target. That’s your job!

For simplicity, the grid is modeled as a tall rectangle filled with mostly-open spaces (each represented by ‘.’), impassable obstacles (each represented by ‘X’), and targets (each represented by ‘T’).

A ball is launched randomly with uniform probability into one of the mostly-open spaces on the top row of the grid. From that point on, collisions with pegs cause the ball to randomly bounce up, down, left, or right, with various given probabilities. For simplicity, assume these probabilities are the same for every space in the grid. If the ball bounces into an obstacle or attempts to move off the grid, it won’t actually move from its current space. When the ball moves into a target it is removed from play.

You can safely assume that the average number of spaces visited by a ball before hitting a target will not exceed \(10^{9}\). It would not make for a very enjoyable game if the ball just bounces forever!

For each target, calculate the probability that it is the one hit by a launched ball.

输入格式

The input consists of a single test case. The first line contains integers \(w\) and \(h\), which are the width and height of the Pachinko grid (\(1 \leq w \leq 20\) and \(2 \leq h \leq 10\, 000\)). The next line contains four non-negative integers \(u\), \(d\), \(l\), and \(r\), which sum to 100 and are the percentage probabilities of the ball bouncing up, down, left, or right from any open space.

Each of the next \(h\) lines contains \(w\) characters, each of which is ‘.’, ‘X’, or ‘T’. These lines describe the Pachinko grid. The first line, which describes the top row of the grid, contains at least one ‘.’ and no ‘T’s.

输出格式

Display one line for each ‘T’ in the grid, in order from top to bottom, breaking ties left to right. For each target, display the probability that a launched ball will hit it. Give the answer with an absolute error of at most \(10^{-6}\).

样例 #1

样例输入 #1

3 2
20 20 20 40
X.X
T.T

样例输出 #1

0.333333333
0.666666667

样例 #2

样例输入 #2

4 5
12 33 28 27
....
.XX.
....
T..T
XTTX

样例输出 #2

0.435853889
0.403753221
0.081202502
0.079190387

提示

Time limit: 5000 ms, Memory limit: 1048576 kB.

高斯消元？ \((nm^3)\) 会直接寄掉。

然后发现如果把一个点 \(i,j\) 标号为 \(i*m+j\) 的话，那么点 \(s\) 只会在 \(s\pm m\) 以内才会有值。（听说这种矩阵叫 Band-Matrix）

消元时可以只消第 \(i\) 行上下 \(m\) 行，消元时也只消有元的那 \(m\) 列，复杂度是 \(O(nm^3)\)

注意消元时如果使用高斯-约旦消元的话，那么会破坏矩阵性质，要用有会带的那种消元。

在记录的时候可以把矩阵 \(i\) 行 \(j\) 列记到 \(i,j-i+m\)，这样子就只用记录 \(2nm\) 个值。

在矩阵消元时如果遇到 0，当且仅当这个点和第一行不连通，可以 continue 掉。回代时也是，输出时可能要特判。

#include<bits/stdc++.h>
using namespace std;
const int N=21,M=10005;
const double eps=1e-9;
int n,m,c;
char s[M][N];
double u,d,l,r,mp[N*M][N*4],ans[N*M],p;
int main()
{
	scanf("%d%d%lf%lf%lf%lf",&m,&n,&u,&d,&l,&r);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='X')
				mp[(i-1)*m+j][m]=1;
			else
			{
				if(i==1)
					++c; 
				double g=0;
				if(s[i][j]=='.') 
				{
					if(i^n&&s[i+1][j]^'X')
						g+=d;
					if(i^1&&s[i-1][j]^'X')
						g+=u;
					if(j^1&&s[i][j-1]^'X')
						g+=l;
					if(j^m&&s[i][j+1]^'X')
						g+=r;
					if(i^n&&s[i+1][j]^'X')
						mp[i*m+j][0]=d/g;
					if(i^1&&s[i-1][j]^'X')
						mp[(i-2)*m+j][2*m]=u/g;
					if(j^1&&s[i][j-1]^'X')
						mp[(i-1)*m+j-1][m+1]=l/g;
					if(j^m&&s[i][j+1]^'X')
						mp[(i-1)*m+j+1][m-1]=r/g;
				}
				mp[(i-1)*m+j][m]=-1;
			}
		}
	}
	for(int i=1;i<=m;i++)
		if(s[1][i]=='.')
			ans[i]=-1.0/c; 
	for(int i=1;i<=n*m;i++)
	{
//		printf("%lf",mp[i][m]);
		if(fabs(mp[i][m])<=eps)
			continue; 
//		printf("%lf",mp[i][m]);
		for(int j=i+1;j<=min(i+m,n*m);j++)
		{
			double s=mp[j][m-j+i]/mp[i][m];
			for(int k=m;k<=2*m;k++)
				mp[j][k-j+i]-=s*mp[i][k];
			ans[j]-=ans[i]*s;
		}
	}
	for(int i=n*m;i;i--)
	{
		for(int j=i+1;j<=min(i+m,n*m);j++)
			ans[i]-=mp[i][m+j-i]*ans[j];
		if(fabs(mp[i][m])>eps)
			ans[i]/=mp[i][m];
		else
			ans[i]=0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='T')
				printf("%.10lf\n",ans[(i-1)*m+j]),p+=ans[(i-1)*m+j];
	assert(fabs(1-p)<=eps);	
}