F. Honeycomb（icpc焦作）

F. Honeycomb

题意

1e3*1e3的蜂巢状网格，已知起点和终点，询问最少步数，无法到达输出- 1

题解

显然可以通过BFS求解，对于蜂巢路径部分做如下处理：

对于每个蜂巢格子的中心做标记，编号

对于每个格子，预处理六个方向，遍历六个方向，并且将可以到达的格子序号，存入当前格子的vector

从而可以得到格子间的关系，BFS即可。

代码

#include
#define ll long long
using namespace std;
const int maxn = 2e6 + 10;
int T, n, m;
int dx[10] = { -2,-1,1,2,1,-1 };
int dy[10] = { 0,3,3,0,-3,-3 };string mp[4010];
vector<int>vec[maxn];
bool vis[maxn];
int fg[5010][7010];int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> T;while (T--) {int S = 0, T = 0, ans = -1, f = 0;cin >> n >> m;getline(cin, mp[1]);for (int i = 1; i <= 4 * n + 3; i++) {getline(cin, mp[i]);mp[i] = ' ' + mp[i];}for (int i = 1; i <= 4 * n + 1; i++) {for (int j = 1; j <= mp[i].size(); j++) {int ff = 0;if (i % 4 == 3 && j % 12 == 5) {fg[i][j] = ++f;ff = 1;vis[f] = 0, vec[f].clear();}else if (i >= 5 && j >= 11 && i % 4 == 1 && j % 12 == 11) {fg[i][j] = ++f;ff = 1;vis[f] = 0, vec[f].clear();}else fg[i][j] = 0;if (mp[i][j] == 'S')S = f;if (mp[i][j] == 'T')T = f;}}for (int i = 1; i <= 4 * n + 1; i++) {for (int j = 1; j <= mp[i].size(); j++) {if (fg[i][j]) {//cout << "U: "<//cout << "V:";for (int k = 0; k < 6; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= 4 * n + 3 && y >= 1 && y <= mp[x].size() && mp[x][y] == ' ') {vec[fg[i][j]].push_back(fg[x + dx[k]][y + dy[k]]);//cout << fg[{x + dx[k], y + dy[k]}] << " ";}}//cout << "\n";}}}queue<pair<int, int>>que;while (!que.empty())que.pop();que.push({ S,1 });vis[S] = 1;while (!que.empty()) {int u = que.front().first, step = que.front().second; que.pop();if (u == T) {ans = step;break;}for (auto v : vec[u]) {if (vis[v])continue;vis[v] = 1;que.push({ v,step + 1 });}}cout << ans << "\n";}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！