Description

一个n∗mn * m的地图，地图中’B’表示小B最初所在的位置；’+’表示空地；’#’表示障碍物(边界也为'')，小B若进入这里则会被遣送会他原来所在的位置(不是初始位置)，并耗费1步；’?’代表着未知，它会将小B传送到随机的另外一个’?’处，’?’的数量等于0或大于等于2；G’表示小B大哥的金牌，找到’G’就可能找到他的大哥。当小B选定一个方向时，他只有p的概率能到达他想去的方向，而到达剩下三个方向则分别有 的概率。小B想尽快找到他的大哥，所以问你最优情况下从’B’到’G’的期望步数是多少。

Constraints

1≤n≤m≤20,0≤p≤11\leq n\leq m \leq 20, 0\leq p \leq 1

Solution

设dis[i][j]dis[i][j]表示起点在(i,j)的答案，初始为inf，所有GG的disdis值为0

我们从所有的GG开始bfs，将bfs到的除了#之外的点加入一个vector

那么我们就能处理出一个bfs顺序的vector了（如果搜索到第一个?,那么需要将剩下所有的?都加入）

接下来，我们按照vector的顺序，不断循环更新每个点的disdis值

  • 如果当前字符不是?，那么枚举想去的方向并枚举实际去的方向统计答案

    特别的，如果实际去的方向为#，那么显然还会留在原地

    设最终答案为ansans，不算留在原地的答案为sumsum，留在原地的概率为staystay，那么有ans=ans∗stay+sumans = ans * stay + sum，移项后有ans=sum1−stayans = \frac{sum}{1-stay}，所以我们在算出sumsum后要除以一个(1−stay)(1 - stay)

  • 如果当前字符为?，那么除了上述过程以外，还需要枚举所有其他的?，新的答案为其他所有?的disdis值的平均值+1

求出新的答案后，与原有的disdis值相比较，如果更小则更新。而如果将整个vector遍历之后没有一个值被更新的话，则说明当前已经是最优解，退出循环输出答案即可。

时间复杂度O(???)O(???)

Debug

  • 60、61L：边界要设成#，不然后面判断会很复杂
  • 106L：pp一开始写成了int

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

const int Maxn = 20 + 10;
const double eps = 1e-5;

inline char safe_getchar()
{
	char ch = getchar();
	while (ch != '#' && ch != 'B' && ch != '#' && ch != '?' && ch != 'G' && ch != '+') ch = getchar();
	return ch;
}

vector <pii> gate, vec;
queue <pii> Q;
int N, M, dr[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
char A[Maxn][Maxn];
double P, Dis[Maxn][Maxn];
int Vis[Maxn][Maxn];

int main()
{
	freopen("find.in", "r", stdin);
	freopen("find.out", "w", stdout);
	N = read(), M = read();
	scanf("%lf", &P);
	int sx, sy;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
		{
			Dis[i][j] = 1e5;
			A[i][j] = safe_getchar();
			if (A[i][j] == '?') gate.pb(mp(i, j));
			else if (A[i][j] == 'G') Q.push(mp(i, j)), Vis[i][j] = 1, Dis[i][j] = 0.0;
			else if (A[i][j] == 'B') sx = i, sy = j;
		}
/**/for (int i = 0; i <= M + 1; ++i) A[0][i] = A[N + 1][i] = '#';
/**/for (int i = 0; i <= N + 1; ++i) A[i][0] = A[i][M + 1] = '#';
	while (!Q.empty())
	{
		pii x = Q.front(); Q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int dx = x.x + dr[i][0], dy = x.y + dr[i][1];
			if (dx <= 0 || dy <= 0 || dx > N || dy > M || Vis[dx][dy] || A[dx][dy] == '#') continue;
			Q.push(mp(dx, dy));
			Vis[dx][dy] = 1;
			vec.pb(mp(dx, dy));
		}
		if (A[x.x][x.y] == '?')
		{
			for (int i = 0; i < gate.size(); ++i)
			{
				int dx = gate[i].x, dy = gate[i].y;
				if (Vis[dx][dy]) continue;
				Q.push(mp(dx, dy));
				Vis[dx][dy] = 1;
				vec.pb(mp(dx, dy));
			}
		}
	}
//	for (int i = 0; i < vec.size(); ++i) cout<<vec[i].x<<" "<<vec[i].y<<endl;
	while (1)
	{
		int fl = 0;
		for (int i = 0; i < vec.size(); ++i)
		{
			pii now = vec[i];
			double ans = 1e5, sum, stay;
			for (int j = 0; j < 4; ++j)
			{
				sum = stay = 0;
				for (int k = 0; k < 4; ++k)
				{
					int dx = now.x + dr[k][0], dy = now.y + dr[k][1];
					if (j == k)
					{
						if (A[dx][dy] == '#') stay += P;
						else sum += Dis[dx][dy] * P;
					}
					else
					{
/**/					double pp = (1.0 - P) / 3.0;
						if (A[dx][dy] == '#') stay += pp;
						else sum += Dis[dx][dy] * pp;
					}
				}
				sum += 1;
				if (stay < 1.0 - eps) sum /= (1.0 - stay);
				else sum = 1e5;
				if (sum < ans - eps) ans = sum;
			}
			if (A[now.x][now.y] == '?')
			{
				sum = 0;
				for (int j = 0; j < gate.size(); ++j)
				{
					pii tmp = gate[j];
					if (tmp.x == now.x && tmp.y == now.y) continue;
					sum += Dis[tmp.x][tmp.y];
				}
				sum /= (1.0 * gate.size() - 1);
				sum += 1;
				if (sum < ans - eps) ans = sum;
			}
			if (ans < Dis[now.x][now.y] - eps) Dis[now.x][now.y] = ans, fl = 1;
		}
		if (!fl) break;
	}
	printf("%.2lf\n", Dis[sx][sy]);
	return 0;
}