赞
踩
参考博客:http://www.xuebuyuan.com/2176887.html
第一种方法:BFS+状态压缩:(700+ms)
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<cmath>
- #include<queue>
- using namespace std;
-
- const int maxn = 55;
- struct node{
- int x, y; //坐标位置
- int key; //用10位二进制来标识拿到了的珠宝
- int t; //已经用的时间
- }s, u, v;
-
- char G[maxn][maxn];//地图
- int val[11]; //存储珠宝的价值
- bool vis[1100][maxn][maxn]; //存储最多十种珠宝所对应的各种状态下的地图,即一维要1<<10,即11位, 用后面十位标识各种状态
- int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//上下左右
- int Ex, Ey, W, H, L, M, ans; //终点、宽、高、时间、珠宝数、答案
-
- int counter = 0;
-
-
- int cal(int key) {//计算当前珠宝状态对应的总价值
- int ret = 0;
- for(int i = 0, j = 1; i < 10; i++, j *= 2)
- if(j&key) ret += val[i];
- return ret;
- }
-
- bool check(int x, int y) {
- return x < H && x >= 0 && y < W && y >= 0; //把这里的W写成了M, 坑了我好长时间
- }
-
- void bfs() {
- queue<node> que;
- que.push(s);
- while(!que.empty()) {
- u = que.front();
- // printf("出来的点 (%d, %d) cal == %d t = %d u.key=%d\n", u.x, u.y, cal(u.key), u.t, u.key);
- que.pop();
- for(int i = 0; i < 4; i++) {
- v.x = u.x + dir[i][0];
- v.y = u.y + dir[i][1];
- // printf("(%d, %d)\n", v.x, v.y);
- if(check(v.x, v.y) && G[v.x][v.y] != '*') {
- if(G[v.x][v.y] != '.') v.key = (u.key | (1 << (G[v.x][v.y] - 'A')));//用按位或更新宝物状态
- else v.key = u.key;
- if(!vis[v.key][v.x][v.y]) { //只访问没有访问过的状态
- vis[v.key][v.x][v.y] = true; //状态访问标记更新
- v.t = u.t + 1; //时间代价+1
- // printf("(%d, %d) cal == %d t = %d\n", v.x, v.y, cal(v.key), v.t);
- if(v.x == Ex && v.y == Ey) ans = max(ans, cal(v.key)); //每一次到达终点的时候更新一下获得珠宝的最大值
- if(v.t < L) {que.push(v); //如果还没到达要求时间,就继续入队
- // cout << "进去的点 :" << v.x << ", " << v.y << endl;
- }
- }
- }
- }
- }
- if(ans == -1) printf("Impossible\n");
- else printf("The best score is %d.\n", ans);
- }
-
- int main() {
- int T; scanf("%d", &T);
- int cas = 0;
- while(T--) {
- scanf("%d%d%d%d", &W, &H, &L, &M);
- for(int i = 0; i < M; i++) {
- scanf("%d", &val[i]);
- }
- for(int i = 0; i < H; i++) scanf("%s", G[i]);
- for(int i = 0; i < H; i++)
- for(int j = 0; j < W; j++){
- if(G[i][j] == '@'){
- s.x = i; s.y = j;
- s.key = 0; s.t = 0;
- G[i][j] = '.';
- }
- else if(G[i][j] == '<') {
- Ex = i; Ey = j;
- G[i][j] = '.';
- }
- }
- // cout << G[Ex][Ey] << endl;
- // cout << s.x << " " << s.y << " " << Ex << " " << Ey << endl;
- // for(int i = 0; i < 4; i++) printf("%s\n", G[i]);
- //初始化-----------------------
- memset(vis, false, sizeof(vis));
- vis[0][s.x][s.y] = true;
- ans = -1;
- printf("Case %d:\n", ++cas);
- bfs();
- if(T!=0) printf("\n");
- }
- return 0;
- }
将珍宝状态压缩,对于l个珍宝,我们可以用l位二进制表示珍宝的获取情况(1表示已经获得,0表示未获得)。然后我们用vis[i][j][k]表示状态,i表示珍宝获取情况,(j,k)表示位置。这样我们相当于走2^l张地图,每次得到珍宝时转换地图,这样就需要相当多的时间消耗了。
第二种方法:DFS+BFS:(31ms)
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<queue>
- #include<cmath>
- using namespace std;
-
- const int INF = 1e8;
- const int maxn = 55;
- struct node{
- int x, y;
- int t;
- }s, u, v;
-
- char G[maxn][maxn];
- bool vis[maxn][maxn], vis2[12];
- int path[12][12], val[12];
- int W, H, L, M;
- int sum, ans; // 所有珠宝总值, 能获得的最大总值
- int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
-
- void bfs(int x, int y, int from) {
- memset(vis, false, sizeof(vis));
- s.x = x; s.y = y; s.t = 0;
- vis[s.x][s.y] = true;
- queue<node> que;
- que.push(s);
- while(!que.empty()) {
- u = que.front(); que.pop();
- for(int i = 0; i < 4; i++) {
- v.x = u.x + dir[i][0];
- v.y = u.y + dir[i][1];
- if(v.x < 0 || v.x >= H || v.y < 0 || v.y >= W || G[v.x][v.y] == '*' || vis[v.x][v.y]) continue;
- vis[v.x][v.y] = true;
- v.t = u.t + 1;
- if(G[v.x][v.y] != '.') {
- if(G[v.x][v.y] == '@') path[from][0] = v.t;
- else if(G[v.x][v.y] == '<') path[from][M+1] = v.t;
- else path[from][G[v.x][v.y]-'A'+1] = v.t;
- }
- que.push(v);
- }
- }
- }
-
- void dfs(int cur, int value, int time) { //当前出发位置, 当前得到珠宝价值, 当前已经用了的时间
- if(time > L || ans == sum) return ;
- if(cur == M+1) { //M+1是终点
- ans = max(ans, value); return ;
- }
- for(int i = 1; i <= M+1; i++) {
- if(vis2[i]) continue;
- vis2[i] = true;
- dfs(i, value+val[i-1], time+path[cur][i]);
- vis2[i] = false;
- }
- }
-
- int main() {
- int T; scanf("%d", &T);
- int cas = 0;
- while(T--) {
- sum = 0;
- scanf("%d%d%d%d", &W, &H, &L, &M);
- for(int i = 0; i < M; i++) {
- scanf("%d", &val[i]);
- sum += val[i];
- }
- val[M] = 0;
- for(int i = 0; i < H; i++) scanf("%s", G[i]);
- for(int i = 0; i <= M+1; i++)
- for(int j = 0; j <= M+1; j++)
- path[i][j] = INF;
- for(int i = 0; i < H; i++)
- for(int j = 0; j < W; j++) {
- if(G[i][j] == '.' || G[i][j] == '*') continue;
- if(G[i][j] == '@') bfs(i, j, 0);
- else if(G[i][j] == '<') bfs(i, j, M+1);
- else if(G[i][j] <= 'J' && G[i][j] >= 'A') bfs(i, j, G[i][j]-'A'+1);
- }
- ans = -1;
- memset(vis2, false, sizeof(vis2));
- dfs(0, 0, 0);
- printf("Case %d:\n", ++cas);
- if(ans == -1) printf("Impossible\n");
- else printf("The best score is %d.\n", ans);
- if(T) printf("\n");
- }
- return 0;
- }
珍宝至多10件,我们可以找出起点到所有珍宝和终点的最短路径,珍宝到其他珍宝和终点的最短路径。需要bfs地图至多21次,比上面的2^l次要少很多。我们得到所有的最短路径之后就可以用dfs搜索最大能获得价值了。
提示:可以用sum保存所有珍宝的价值和,要是dfs时,答案ans=sum,那么就可以剪枝掉了,why?因为没有比这个价值更大的了。
注意:我们需要把所有的最短路径path[i][j]初始化为无穷大,因为可能出现走不到的情况。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。