hdu 3681 PrisonBreak 状压+bfs求最短+dfs+二分答案

缘起

这是一道有想法的题目~ HDU 3681 PrisonBreak

分析

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
一个机器人身处N*M的矩阵中,它想要越狱逃出来,这个矩阵由N行M列的字符组成,含义如下:

(1) S表示空格子

(2) F表示机器人的起始位置

(3) G表示能量池,对于同一个能量池只能使用一次,且经过能量池的时候可以选择用或者不用,用的话能量就会变满.

(4) D表示坏格子,机器人不能走D格子

(5) Y表示开关格子,机器人必须把所有开关格子至少走一遍才能成功越狱.

机器人每走一步消耗1点能量,现在求它初始时应该带多大的容量的电池.要求该电池的容量在能使它越狱成功的条件下
尽量小.

输入:包含多组实例,以0 0表示结束.每个实例第一行是N*M(1<=n,m<=15),然后是N行M列的字符矩阵.其中能量池
和开关的总数不超过15.

输出:电池的最小容量.如果不能逃脱,输出-1.

样例输入
5 5
GDDSS
SSSFS
SYGYS
SGSYS
SSYSS
0 0

样例输出
4

限制
2s 32MB

首先, 我先声明, 自己想了一会儿此题没想出来. 看了神犇【1】的题解. 思路是这样的. 其实S和D不考虑. 本题实际格子只有F、G、Y三种（下面将其称为关键点）. 首先用bfs预处理出F、Y、G这<=16个点之间的最短路径. 而G只能使用一次. 所以除非我们指明要到G，我们的路径中哪怕经过G也不会去使用能量池的。所以题目的图抽象成F、G、Y三类点的无向图. 注意, 如果在求F到Y的最短距离为不可达的话, 则答案一定是-1. 否则答案一定不是-1. 假设通过bfs预处理得到的图为g， 下面简称g为新图.

题目要求的是g上从F出发. 经过所有的Y，每个G至多经过1次所需要的最少电池容量.

注意, 因为每次使用能量池,机器人的电量将恢复初始电量, 所以这和初始电量有关. 所以我们需要二分答案. 而二分答案就涉及上下界, 下界好说,显然是0, 上界我们YY成300即可（其实有一种办法就是在bfs得到F到各个Y的最短距离之和*2 即可以作为二分答案的上界, 但是懒得弄了）

则每次二分答案的时候, 本质上就是询问初始关键点状态值为 s（关键点个数<=16, 尚未去过记做1，去过了记做0，则显然我们可以用二进制压缩刻画关键点集的遍历情况）时, 目前在i号关键点, 而且目前电量为x时能否完成任务呗? 那这不就是一个dfs吗?

讲了这么多, 就可以开心的切代码了

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,g[20][20],t[20],tx[20], ty[20], cnt,mapp[20][20],f,full, fe; // g是新图(无向图), cnt是关键点的个数,t[i]表示第i个点到底是F还是Y还是G, 其中F用0表示, Y用1表示,G用2表示, tx和ty表示这些关键点的坐标,mapp是原图关键点格子对应到第几个关键格子的映射
char mp[20][20];
bool v[20][20];

void bfs(int i)
{
	memset(v,0,sizeof(v));
	struct Node
	{
		int x,y,len;
		Node(int x,int y, int len):x(x),y(y),len(len){}
	};
	queue<Node> q;
	v[tx[i]][ty[i]] = true;
	q.push(Node(tx[i], ty[i],0));
	while (!q.empty())
	{
		Node front = q.front();
		q.pop();
		if (mp[front.x][front.y]=='F' || mp[front.x][front.y] =='Y' || mp[front.x][front.y]=='G')
		{
			g[i][mapp[front.x][front.y]] = g[mapp[front.x][front.y]][i] =  front.len;
		}
		for (int k = 0,nxti,nxtj;k<4;k++)
		{
			nxti = front.x+dir[k][0];
			nxtj = front.y+dir[k][1];
			if (~nxti && nxti<n && ~nxtj && nxtj<m && !v[nxti][nxtj] && mp[nxti][nxtj]!='D') // 如果下一个格子不是D而且不越界,而且还没访问
			{
				v[nxti][nxtj] = true;
				q.push(Node(nxti, nxtj, front.len+1));
			}
		}
	}
}

bool ok()
{
	for (int i = 0;i<cnt; i++)
	{
		if (!~g[f][i] && mp[tx[i]][ty[i]] =='Y') // 不可到达的Y
		{
			return false;
		}
	}
	return true;
}

bool dd(int s) // s是不是终结状态?
{
	for (int i = 0;i<cnt;i++)
	{
		if (t[i]==1 && (s>>i&1)) // 是Y
		{
			return false;
		}
	}
	return true;
}

bool dfs(int s, int i, int x) // s状态,而且在i顶点, 剩余电量是x, 能不能完成任务?
{
	if (dd(s) && x>=0)
	{
		return true;
	}
	for (int j = 0,nxts;j<cnt;j++) // 状态转移
	{
		if (j==i) // 不能到自己
		{
			continue;
		}
		if (t[j] == 2 && !(s>>j&1)) // 如果是G, 而且已经到过一次了
		{
			continue;
		}
		if (!~g[i][j] || x<g[i][j]) // 如果j可以到达但是能量不足以支撑走到j或者j根本到不了
		{
			continue;
		}
		nxts = s & ~(1<<j); // 转移后的状态
		if (t[j]!=2 && dfs(nxts, j, x-g[i][j])) // 如果下一个状态不是能量池, 则能量降低
		{
			return true;
		}
		if (t[j]==2 && dfs(nxts, j, fe)) // 如果下一个状态是能量池的话, 则能量恢复到fe(即初始能量)
		{
			return true;
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		memset(g, -1, sizeof(g));
		cnt = 0;
		for (int i = 0;i<n;i++)
		{
			char c = getchar();
			for (int j = 0;j<m;j++)
			{
				mp[i][j] = getchar();
				if (mp[i][j]=='S' || mp[i][j] == 'D')
				{
					continue;
				}
				switch(mp[i][j])
				{
				case 'F':
					t[f = cnt] = 0; // f记录了出发的格子到底是第几个关键格子
					break;
				case 'Y':
					t[cnt] = 1;
					break;
				case 'G':
					t[cnt] = 2;
					break;
				default:
					break;
				}
				mapp[i][j] = cnt;
				tx[cnt] = i, ty[cnt] = j;
				++cnt;
			}
		}
		for (int i = 0;i<cnt;i++)
		{
			bfs(i); // 从第i个关键格子出发进行bfs,得到新图的邻接矩阵g
		}
		if (!ok()) // 有从F出发无法到达的Y
		{
			puts("-1");
			continue;
		}
		full = ((1<<cnt)-1)&~(1<<f); // 出发点显然是已经到过了的
		int lo = 0, hi = 300, mid,ans = -1;
		while(lo<=hi)
		{
			mid = lo+hi>>1;
			fe = mid;
			if (dfs(full, f, mid))
			{
				ans = mid;
				hi = mid-1;
			}
			else
			{
				lo = mid+1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

但是很遗憾, 被T掉了. 但是和ac代码对拍过, 不会wa的. 只是超时. 因为明眼人一看就知道——我他喵的写成了dfs了（而不是dp,也不是记忆化）.即判断当前状态是(i,j,x)的时候（即当前遍历过的点的状态是i, j是当前位于的点, x是当前拥有的电量）能不能完成任务.

显然被T掉的原因在于大量的状态被重复计算了.

所以我们尝试对dfs的结果进行记忆化

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,g[20][20],t[20],tx[20], ty[20], cnt,mapp[20][20],f,full, fe;
char mp[20][20];
bool v[20][20];

void bfs(int i)
{
	memset(v,0,sizeof(v));
	struct Node
	{
		int x,y,len;
		Node(int x,int y, int len):x(x),y(y),len(len){}
	};
	queue<Node> q;
	v[tx[i]][ty[i]] = true;
	q.push(Node(tx[i], ty[i],0));
	while (!q.empty())
	{
		Node front = q.front();
		q.pop();
		if (mp[front.x][front.y]=='F' || mp[front.x][front.y] =='Y' || mp[front.x][front.y]=='G')
		{
			g[i][mapp[front.x][front.y]] = g[mapp[front.x][front.y]][i] =  front.len;
		}
		for (int k = 0,nxti,nxtj;k<4;k++)
		{
			nxti = front.x+dir[k][0];
			nxtj = front.y+dir[k][1];
			if (~nxti && nxti<n && ~nxtj && nxtj<m && !v[nxti][nxtj] && mp[nxti][nxtj]!='D') 
			{
				v[nxti][nxtj] = true;
				q.push(Node(nxti, nxtj, front.len+1));
			}
		}
	}
}

bool ok()
{
	for (int i = 0;i<cnt; i++)
	{
		if (!~g[f][i] && mp[tx[i]][ty[i]] =='Y') 
		{
			return false;
		}
	}
	return true;
}

bool dd(int s) 
{
	for (int i = 0;i<cnt;i++)
	{
		if (t[i]==1 && (s>>i&1)) 
		{
			return false;
		}
	}
	return true;
}

int kkk[1<<16][16][300]; // 对dfs进行记忆化

bool dfs(int s, int i, int x) 
{
	if (~kkk[s][i][x])
	{
		return kkk[s][i][x];
	}
	if (dd(s) && x>=0)
	{
		return kkk[s][i][x] = 1;
	}
	for (int j = 0,nxts;j<cnt;j++) 
	{
		if (j==i)
		{
			continue;
		}
		if (t[j] == 2 && !(s>>j&1)) 
		{
			continue;
		}
		if (!~g[i][j] || x<g[i][j]) 
        {
			continue;
		}
		nxts = s & ~(1<<j);
		if (t[j]!=2 && dfs(nxts, j, x-g[i][j]))
        {
			return kkk[s][i][x] = 1;
		}
		
		if (t[j]==2 && dfs(nxts, j, fe))
		{
			return kkk[s][i][x] = 1;
		}
	}
	return kkk[s][i][x] = 0;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		memset(g, -1, sizeof(g));
		cnt = 0;
		for (int i = 0;i<n;i++)
		{
			char c = getchar();
			for (int j = 0;j<m;j++)
			{
				mp[i][j] = getchar();
				if (mp[i][j]=='S' || mp[i][j] == 'D')
				{
					continue;
				}
				switch(mp[i][j])
				{
				case 'F':
					t[f = cnt] = 0; 
					break;
				case 'Y':
					t[cnt] = 1;
					break;
				case 'G':
					t[cnt] = 2;
					break;
				default:
					break;
				}
				mapp[i][j] = cnt;
				tx[cnt] = i, ty[cnt] = j;
				++cnt;
			}
		}
		for (int i = 0;i<cnt;i++)
		{
			bfs(i); 
		}
		if (!ok()) 
		{
			puts("-1");
			continue;
		}
		full = ((1<<cnt)-1)&~(1<<f); 
		int lo = 0, hi = 300, mid,ans = -1;
		while(lo<=hi)
		{
			mid = lo+hi>>1;
			fe = mid;
			memset(kkk,-1,sizeof(kkk)); // 每次都要memset!
			if (dfs(full, f, mid))
			{
				ans = mid;
				hi = mid-1;
			}
			else
			{
				lo = mid+1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

结果毫无意外~ MLE掉了~ 因为上面的kkk则需要的空间是(1<<16)*16*300*4字节, 达到了800+MB， 这显然会MLE掉.

而且实测还是很慢! 究其原因是因为上面的代码第162行每次都要重置kkk, 不同fe=mid情况下 kkk[s][i][x] 是不能复用的! 因为例如都是 (s=1824, i = 7, x = 3), 但是一个fe是5， 一个fe是74, 而到达下一个G格子只需要3个能量, 则fe=5的情况到达下一个G格子就只有5个能量, 未必能完成越狱， 但是fe=74的情况下, 到达下一个G格子就能有74的能量, 几乎可以通杀全场了. 所以每次都要memset整个kkk （不然算法就是错的!）. 而一旦每次二分的时候都memset的话, 算法的速度自然降下来了. 但是对拍过, 应该也不会wa. 只是慢

How?

其实debug的时候就发现为毛上面两份代码都那么的慢了~ 因为总会出现A->B, 然后B又回到A的情形发生！但是和【2】一样, 我们已经预处理出两点之间的最短路了（【2】是通过floyd，而本题是通过bfs）, 所以和【2】一样——已经遍历过的点不需要再去遍历了（特别的，对于G格子，即能量池）. 所以可以在上面第一份代码的基础上稍微改动一下就能A了

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,g[20][20],t[20],tx[20], ty[20], cnt,mapp[20][20],f,full, fe;
char mp[20][20];
bool v[20][20];

void bfs(int i)
{
	memset(v,0,sizeof(v));
	struct Node
	{
		int x,y,len;
		Node(int x,int y, int len):x(x),y(y),len(len){}
	};
	queue<Node> q;
	v[tx[i]][ty[i]] = true;
	q.push(Node(tx[i], ty[i],0));
	while (!q.empty())
	{
		Node front = q.front();
		q.pop();
		if (mp[front.x][front.y]=='F' || mp[front.x][front.y] =='Y' || mp[front.x][front.y]=='G')
		{
			g[i][mapp[front.x][front.y]] = g[mapp[front.x][front.y]][i] =  front.len;
		}
		for (int k = 0,nxti,nxtj;k<4;k++)
		{
			nxti = front.x+dir[k][0];
			nxtj = front.y+dir[k][1];
			if (~nxti && nxti<n && ~nxtj && nxtj<m && !v[nxti][nxtj] && mp[nxti][nxtj]!='D') 
			{
				v[nxti][nxtj] = true;
				q.push(Node(nxti, nxtj, front.len+1));
			}
		}
	}
}

bool ok()
{
	for (int i = 0;i<cnt; i++)
	{
		if (!~g[f][i] && mp[tx[i]][ty[i]] =='Y') 
		{
			return false;
		}
	}
	return true;
}

bool dd(int s)
{
	for (int i = 0;i<cnt;i++)
	{
		if (t[i]==1 && (s>>i&1)) 
		{
			return false;
		}
	}
	return true;
}

bool dfs(int s, int i, int x) 
{
	if (dd(s) && x>=0)
	{
		return true;
	}
	for (int j = 0,nxts;j<cnt;j++) 
	{
		if (!(s>>j&1)) // 已经遍历过的点不要再去了,特别的, 能量池不需要再去了
		{
			continue;
		}
		if (!~g[i][j] || x<g[i][j])
		{
			continue;
		}
		nxts = s & ~(1<<j); 
		if (t[j]!=2 && dfs(nxts, j, x-g[i][j]))
		{
			return true;
		}
		if (t[j]==2 && dfs(nxts, j, fe)) 
		{
			return true;
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		memset(g, -1, sizeof(g));
		cnt = 0;
		for (int i = 0;i<n;i++)
		{
			char c = getchar();
			for (int j = 0;j<m;j++)
			{
				mp[i][j] = getchar();
				if (mp[i][j]=='S' || mp[i][j] == 'D')
				{
					continue;
				}
				switch(mp[i][j])
				{
				case 'F':
					t[f = cnt] = 0; 
					break;
				case 'Y':
					t[cnt] = 1;
					break;
				case 'G':
					t[cnt] = 2;
					break;
				default:
					break;
				}
				mapp[i][j] = cnt;
				tx[cnt] = i, ty[cnt] = j;
				++cnt;
			}
		}
		for (int i = 0;i<cnt;i++)
		{
			bfs(i);
		}
		if (!ok()) 
		{
			puts("-1");
			continue;
		}
		full = ((1<<cnt)-1)&~(1<<f); 
		int lo = 0, hi = 300, mid,ans = -1;
		while(lo<=hi)
		{
			mid = lo+hi>>1;
			fe = mid;
			if (dfs(full, f, mid))
			{
				ans = mid;
				hi = mid-1;
			}
			else
			{
				lo = mid+1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况（比【1】大佬的板子快了~10倍）

Status Accepted
Time 15ms
Memory 1260kB
Length 2588
Lang G++
Submitted 2019-11-04 10:51:31
Shared
RemoteRunId 31277151

注意, 本题仅仅是状压，而不是状压DP~

参考

【1】https://blog.csdn.net/u013480600/article/details/20065295

【2】https://yfsyfs.github.io/2019/10/31/POJ-3311-Hie-With-The-Pie-TSP-%E7%8A%B6%E5%8E%8BDP/