穿越雷区
January 2, 2025About 3 min
穿越雷区
题目
X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从 A 区到 B 区去（ A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：
A + - + -
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
链接
题解
#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <queue>
using namespace std;
struct State
{
int x, y; // 坐标
int steps; // 步数
bool lastPositive; // 上一个是否为能量
bool isFirst; // 是否为第一步
State(int x, int y, int s, bool lp, bool f) : x(x), y(y), steps(s), lastPositive(lp), isFirst(f) {}
};
struct StateHash
{
/* 访问状态的哈希 */
int x, y;
bool lastPositive;
StateHash(int x, int y, bool lp) : x(x), y(y), lastPositive(lp) {}
bool operator==(const StateHash &other) const
{
return x == other.x && y == other.y && lastPositive == other.lastPositive;
} // 重载OPerator，比较两个StateHash对象是否相等
};
namespace std
{
template <>
struct hash<StateHash>
{
/* data */
size_t operator()(const StateHash &s) const
{
return hash<int>()(s.x) ^ hash<int>()(s.y) ^ hash<bool>()(s.lastPositive);
}
};
}
int findShortestPath(vector<vector<char>> &grid)
{
int n = grid.size();
int startx = -1, starty = -1, endx = -1, endy = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'A')
{
startx = i;
starty = j;
}
else if (grid[i][j] == 'B')
{
endx = i;
endy = j;
}
}
}
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
queue<State> q;
q.push(State(startx, starty, 0, false, true));
unordered_set<StateHash> visited;
while (!q.empty())
{
State curr = q.front();
q.pop();
if (curr.x == endx && curr.y == endy)
{
return curr.steps;
}
// 遍历方向
for (int i = 0; i < 4; i++)
{
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
char next = grid[nx][ny];
if (next == 'B')
{
StateHash sh(nx, ny, curr.lastPositive);
if (visited.find(sh) == visited.end())
{
return curr.steps + 1;
}
}
else if (next == '+')
{
if ((curr.isFirst || !curr.lastPositive))
{
StateHash sh(nx, ny, true);
if (visited.find(sh) == visited.end())
{
visited.insert(sh);
q.push(State(nx, ny, curr.steps + 1, true, false));
}
}
}
else if (next == '-')
{
if ((curr.isFirst || curr.lastPositive))
{
StateHash sh(nx, ny, false);
if (visited.find(sh) == visited.end())
{
visited.insert(sh);
q.push(State(nx, ny, curr.steps + 1, false, false));
}
}
}
}
}
}
return -1;
}
int main()
{
// 请在此输入您的代码
int n;
cin >> n;
vector<vector<char>> map(n, vector<char>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
cout << findShortestPath(map) << endl;
return 0;
}定义结构体，记录当前节点状态
struct State
{
int x, y; // 坐标
int steps; // 步数
bool lastPositive; // 上一个是否为能量
bool isFirst; // 是否为第一步
State(int x, int y, int s, bool lp, bool f) : x(x), y(y), steps(s), lastPositive(lp), isFirst(f) {}
};其中，State(int x, int y, int s, bool lp, bool f) : x(x), y(y), steps(s), lastPositive(lp), isFirst(f) {}是构造结构体函数的语法，等价于:
State(int x, int y, int s, bool lp, bool f) {
this->x = x;
this->y = y;
this->steps = s;
this->lastPositive = lp;
this->isFirst = f;
}记录访问状态的哈希
struct StateHash
{
/* 访问状态的哈希 */
int x, y;
bool lastPositive;
StateHash(int x, int y, bool lp) : x(x), y(y), lastPositive(lp) {}
bool operator==(const StateHash &other) const
{
return x == other.x && y == other.y && lastPositive == other.lastPositive;
} // 重载OPerator，比较两个StateHash对象是否相等
};