A41759. 冠军之路当训练师眼神对上的那一刻，就会开始对战。lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中，'.'代表可以行走的地面，'#'代表无法行走的岩石。'I'代表山洞的入口，即lxz现在所在的位置。'O'表示冠军之路的出口。lxz可以向上下左右四个方向行走。矩形的四周都是山洞的岩石，无法行走。冠军之路中有一些精英训练师，他们可能面向上、下、左、右四个方向，在地图上用'w','a…
填空题
困难
知识点
题目描述
冠军之路
当训练师眼神对上的那一刻，就会开始对战。
lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中，'.'代表可以行走的地面，'#'代表无法行走的岩石。'I'代表山洞的入口，即lxz现在所在的位置。'O'表示冠军之路的出口。lxz可以向上下左右四个方向行走。矩形的四周都是山洞的岩石，无法行走。
冠军之路中有一些精英训练师，他们可能面向上、下、左、右四个方向，在地图上用'w','a','s','d'表示，其中'w'表示向上。's'表示向下。'a'表示向左。'd'表示向右（这些位置不可行走）。如果lxz出现在精英训练师正对方向的一条线上，且没有被岩石或其他精英训练师阻挡，那么lxz就会与这个精英训练师进行对战。每位训练师只会与lxz对战一次。
为了通过冠军之路，lxz必须击败所有精英训练师。lxz希望找到一条击败所有精英训练师并走到冠军之路出口的最短路径。
输入
第一行是两个整数，N, M表示地图的大小。 0 < N, M <= 100 接下来是N行，每行M个字符，代表冠军之路的地图。训练师的个数不超过8
输出
一个整数，表示击败所有精英训练师并走到冠军之路出口的最短路径的长度。如果无法击败所有精英训练师或者无法到达出口，输出-1。
样例输入
3 3
Id.
...
Oa#
样例输出
8
参考答案
#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
using namespace std;
/*
3 3
Id.
...
Oa#
*/
struct point {
int x, y;
point(int x, int y) : x(x), y(y) {}
point() : x(0), y(0) {}
bool operator==(const point &p) const { return x == p.x && y == p.y; }
bool operator<(const point &p) const {
if (x == p.x)
return y < p.y;
return x < p.x;
}
};
struct item {
point pt;
char c;
item(point p, char c) {
pt.x = p.x;
pt.y = p.y;
this->c = c;
}
};
int direct[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int a[105][105];
char d[105][105];
int pass[105][105];
vector<vector<point>> pts;
vector<item> base;
point bp, ep;
int n, m;
int bfs(point from, point to) {
queue<point> q;
char path[105][105] = {0};
q.push(from);
int ans = 0;
while (q.size()) {
// TODO
int size = q.size();
for (int k = 0; k < size; k++) {
point cur = q.front();
q.pop();
path[cur.x][cur.y] = 1;
if (cur == to) {
return ans;
}
for (int i = 0; i < 4; i++) {
point dst;
dst.x = cur.x + direct[i][0];
dst.y = cur.y + direct[i][1];
if (dst.x >= n || dst.x < 0)
continue;
if (dst.y > m || dst.y < 0)
continue;
if (path[dst.x][dst.y] == 0 &&
(d[dst.x][dst.y] == '.' || d[dst.x][dst.y] == 'O' ||
d[dst.x][dst.y] == 'I')) {
q.push(dst);
}
}
}
ans++;
}
return 0;
}
vector<point> getpoints(char pos, point p) {
vector<point> res;
string ss = ".IO";
if (pos == 'w') {
for (int i = p.x - 1; i >= 0; i--)
if (ss.find(d[i][p.y]) != string::npos)
res.push_back(point(i, p.y));
else
break;
}
if (pos == 's') {
for (int i = p.x + 1; i < m; i++)
if (ss.find(d[i][p.y]) != string::npos)
res.push_back(point(i, p.y));
else
break;
}
if (pos == 'a') {
for (int i = p.y - 1; i >= 0; i--)
if (ss.find(d[p.x][i]) != string::npos)
res.push_back(point(p.x, i));
else
break;
}
if (pos == 'd') {
for (int i = p.y + 1; i < n; i++)
if (ss.find(d[p.x][i]) != string::npos)
res.push_back(point(p.x, i));
else
break;
}
return res;
}
/*
void showpath(int i, int j) {
if (i == j) return;
if (pass[i][j] == 0) {
printf("%d -> %d \n",i , j);
route.push_back(j);
} else {
showpath(i, pass[i][j]);
showpath(pass[i][j], j);
}
}
*/
int getMinBfs(point pt, vector<int> &idx, vector<int> &p,
vector<vector<point>> pts) {
int minval = INT32_MAX;
for (uint32_t i = 0; i < pts.size(); i++) {
for (uint32_t j = 0; j < pts[i].size(); j++) {
int dis = bfs(pt, pts[i][j]);
if (minval > dis) {
minval = dis;
idx.clear(), p.clear();
idx.push_back(i), p.push_back(j);
} else if (minval == dis) {
idx.push_back(i), p.push_back(j);
}
}
}
return minval;
}
vector<point> getMinPoints(point pt, vector<vector<point>> pts) {
vector<point> res;
int idx, p;
for (uint32_t i = 0; i < pts.size(); i++) {
int minval = INT32_MAX;
for (uint32_t j = 0; j < pts[i].size(); j++) {
int dis = bfs(pt, pts[i][j]);
if (minval > dis) {
minval = dis;
idx = i, p = j;
}
}
res.push_back(pts[idx][p]);
}
return res;
}
// 贪心法+bfs搜索计算最小路径
int getMinPath(point bp, point ep, vector<vector<point>> points) {
int sum = 0, minSum = INT32_MAX;
vector<int> idx, p;
vector<point> ap;
vector<vector<point>> apt;
point pt;
ap = getMinPoints(bp, points); // 获取与bp点距离最近的所有点
for (int x = 0; x < ap.size(); x++) {
pt = bp;
sum = bfs(pt, ap[x]);
apt = points;
apt.erase(apt.begin() + x);
pt = ap[x]; // 设置为当前点
if (apt.size() > 0) {
sum += getMinBfs(pt, idx, p, apt);
while (1) {
if (idx.size() > 1) { // 有多个并列最近点的情况
int tmin = INT32_MAX, ts, k;
for (int i = 0; i < idx.size(); i++) {
vector<vector<point>> tp = apt;
tp.erase(tp.begin() + idx[i]);
ts = getMinPath(apt[idx[i]][p[i]], ep,
tp); // 计算以并列点为起点的路径
if (tmin > ts) {
tmin = ts;
k = i;
} // 记录最小路径
}
idx[0] = idx[k], p[0] = p[k]; // 更新最小路径
}
pt = apt[idx[0]][p[0]];
apt.erase(apt.begin() + idx[0]);
if (apt.size() == 0)
break;
sum += getMinBfs(pt, idx, p, apt);
}
}
sum += bfs(pt, ep); // 加上到出口点的距离
if (minSum > sum)
minSum = sum;
}
return minSum;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> d[i][j];
if (d[i][j] != '#' && d[i][j] != '.') {
base.push_back(item(point(i, j), d[i][j]));
}
if (d[i][j] == 'I')
bp = point(i, j);
if (d[i][j] == 'O')
ep = point(i, j);
}
// 扩展点，增加同方向的
for (int i = 0; i < base.size(); i++) {
vector<point> vp;
if (base[i].c != 'I' && base[i].c != 'O') {
vp = getpoints(base[i].c, base[i].pt);
pts.push_back(vp);
}
}
int sum1 = getMinPath(bp, ep, pts); // 正向计算
int sum2 = getMinPath(ep, bp, pts); // 反向计算
cout << (sum1 > sum2 ? sum2 : sum1) << endl; // 取最小值
return 0;
}
上一题
下一题