Description：

给一个地图，有一个起点和至少一个终点，有一些大写字母的区域可能是陷阱也可能不是，同一个字母表示的区域相同，给出每种情况是否是陷阱的状态的概率，该开始有血，经过陷阱会掉血，问能从起点走到一个终点的概率。

$1\leqslant n,m\leqslant 30,1\leqslant k\leqslant 5$

Solution：

发现可以用一个三进制来表示状态，即 $0$ 为无危险， $1$ 为有， $2$ 为不知道，先预处理一个 $g[state][k]$ 表示在 $state$ 的状态时下一个走到 $k$ 是陷阱的概率，然后设 $f[x][y][state][h]$ 表示在位置 $(x,y)$ ，状态为 $state$ ，还有 $h$ 血的概率，转移时枚举下一步往哪里走，如果下一个是一个还没确定的，要分别对于往哪个方向走求出两个最大值然后乘上概率。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k,h;

#define MAXN 33

#define MAXK 7

double f[MAXN][MAXN][(1 << 10) + 5][MAXK];

char p[MAXN][MAXN];

int v[1 << MAXK],sumv = 0;

char getc()

{

	register char c = getchar();

	while(c != '.' && c != '#' && c != '$' && c != '@' && !isupper(c))c = getchar();

	return c;

}

double g[1 << (MAXK << 1)][MAXK];

void pre_work()

{

	for(int s = 0;s < (1 << (k << 1));++s)

	{

		bool tag = true;

		for(int i = 1;i <= k;++i)

		{

			int st = (s >> ((i - 1) << 1)) & 3;

			if(st == 3){tag = false;break;}

		}

		if(!tag)continue;

		for(int d = 1;d <= k;++d)

		{

			if(((s >> ((d - 1) << 1)) & 3) != 2)continue;

			int sumw = 0,suml = 0;

			for(int t = 0;t < (1 << k);++t)

			{

				bool flag = true;

				for(int i = 1;i <= k;++i)

				{

					int st = (s >> ((i - 1) << 1)) & 3,tt = (t >> (i - 1)) & 1;

					if(st == 2)continue;

					if((st == 0 && tt == 1) || (st == 1 && tt == 0)){flag = false;break;}

				}

				if(!flag)continue;

				if(t & (1 << (d - 1)))sumw += v[t];

				else suml += v[t];

			}

			g[s][d] = (double)sumw / (double)(sumw + suml);

		}

	}

	return;

}

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

int s[MAXK];

void uncode(int state,int s[])

{

	for(int i = 1;i <= k;++i)

	{

		s[i] = state & 3;

		state = state >> 2;

	}

	return;

}

int decode(int s[])

{

	int res = 0;

	for(int i = k;i >= 1;--i)

	{

		res = res << 2 | s[i];

	}

	return res;

}

bool vis[MAXN][MAXN][1 << (MAXK << 1)][MAXK];

double dp(int x,int y,int state,int blood)

{

	if(x < 1 || x > n || y < 1 || y > m)return 0.0;

	if(p[x][y] == '#')return 0.0;

	if(blood == 0)return 0.0;

	if(vis[x][y][state][blood])return f[x][y][state][blood];

	if(p[x][y] == '@')return 1.0;

	vis[x][y][state][blood] = true;

	double ans = 0.0;

	if(p[x][y] == '$' || p[x][y] == '.')

	{

		for(int i = 0;i < 4;++i)

			ans = max(ans,dp(x + mx[i],y + my[i],state,blood));

	}

	else

	{

		uncode(state,s);

		int cur = p[x][y] - 'A' + 1;

		if(s[cur] == 0)

		{

			for(int i = 0;i < 4;++i)

				ans = max(ans,dp(x + mx[i],y + my[i],state,blood));

		}

		if(s[cur] == 1)

		{

			for(int i = 0;i < 4;++i)

				ans = max(ans,dp(x + mx[i],y + my[i],state,blood - 1));

		}

		if(s[cur] == 2)

		{

			double p1 = 0.0,p2 = 0.0;

			for(int i = 0;i < 4;++i)

			{

				s[cur] = 1;

				p1 = max(p1,dp(x + mx[i],y + my[i],decode(s),blood - 1));

				s[cur] = 0;

				p2 = max(p2,dp(x + mx[i],y + my[i],decode(s),blood));

			}

			ans = p1 * g[state][cur] + p2 * (1.0 - g[state][cur]);

			s[cur] = 2;

		}

	}

	return (f[x][y][state][blood] = ans);

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&k,&h);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			p[i][j] = getc();

	for(int i = 0;i < (1 << k);++i)

		scanf("%d",&v[i]);

	for(int i = 0;i < (1 << k);++i)

		sumv += v[i];

	int sx,sy;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			if(p[i][j] == '$')sx = i,sy = j;

	pre_work();

	memset(f,0xfe,sizeof(f));

	int st;

	for(int i = 1;i <= k;++i)st = st << 2 | 2;

	printf("%.3lf\n",dp(sx,sy,st,h));

	return 0;

}