答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct point {
int x, y;
short keys;
short fighted;
int steps;
short layout;
point(int inx, int iny, short k, short f, int s, short l)
: x(inx), y(iny), keys(k), fighted(f), steps(s), layout(l) {}
};
char flags[105][105][10][130];
int n, m;
int k, q;
char maze[105][105];
vector<pair<int, int>> traps;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int findTraps(int x, int y) {
for (int i = 0; i < q; i++) {
if (traps[i].first == x && traps[i].second == y)
return i;
}
}
int main() {
cin >> n >> m;
int startx, starty;
q = 0;
k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
if (maze[i][j] == 'G') {
q++;
traps.push_back(make_pair(i, j));
}
if (maze[i][j] > '0' && maze[i][j] <= '9')
k = max(k, maze[i][j] - '0');
}
}
queue<point> myqueues;
short oriLayout = (1 << q) - 1;
myqueues.push(point(startx, starty, 0, 0, 0, oriLayout));
memset(flags, 0, sizeof(flags));
flags[startx][starty][0][oriLayout] = 1;
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (maze[top.x][top.y] == 'T' && top.keys == k) {
cout << top.steps << endl;
break;
}
if (maze[top.x][top.y] == 'G' && top.fighted == 0) {
int index = findTraps(top.x, top.y);
short layout = top.layout & (~(1 << index));
myqueues.push(point(top.x, top.y, top.keys, 1, top.steps + 1, layout));
flags[top.x][top.y][top.keys][layout] = 1;
continue;
}
for (int i = 0; i < 4; i++) {
int tx = top.x + dx[i];
int ty = top.y + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if (maze[tx][ty] == 'X')
continue;
else if (maze[tx][ty] == 'G') {
if (flags[tx][ty][top.keys][top.layout])
continue;
int index = findTraps(tx, ty);
if ((top.layout >> index) & 1) // 还没打
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
else
myqueues.push(point(tx, ty, top.keys, 1, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else if (maze[tx][ty] == '.' || maze[tx][ty] == 'S' ||
maze[tx][ty] == 'T') {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else {
int key = maze[tx][ty] - '0';
if (key == top.keys + 1) {
if (flags[tx][ty][key][top.layout])
continue;
myqueues.push(point(tx, ty, key, 0, top.steps + 1, top.layout));
flags[tx][ty][key][top.layout] = 1;
} else {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
}
}
}
}
return 0;
}</pre>
解析
解题思路
思路:广搜题,属于较为复杂的一种,既要收集钥匙也要破坏陷阱。
状态包括:x,y坐标,keys表示现在收集的钥匙种数,fighted表示是否已经消灭陷阱,steps记录此时的步数,layout是陷阱的分布(用short变量表示)。
去重:xy坐标+钥匙+陷阱分布
地图上的标识有
‘.’:平地;‘X’:障碍,不能通过;‘T’:终点;‘S’:起点;‘G’:陷阱;1~9的数字:钥匙
起点和没有拿完钥匙的终点,不能拿的钥匙,破坏完的陷阱都当做平地处理