题解：P17471 [ICPC 2018 Jiaozuo R] Honeycomb

_pig_ · 2026-09-17 21:09:07 · 题解

最短路部分显然可以直接 BFS，难点在于通过神秘输入建图。有一个比较简单的方式，那就是找每一个六边形在字符阵中的中心（也就是 S,T 所在的位置），然后以这个为基准看六条边的坐标。那只需要分列的奇偶找一下中心坐标的规律就做完了。

//By _pig_&_buta_
//Ciallo～(∠・ω< )⌒★
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
#define Testify 2221
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
typedef array <int, 2> arr2;
typedef array <int, 3> arr3;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 1e6 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
string s[4010];
int n, m, sp, tp, d[N];
int Hash(int x, int y) {return ((x - 1) * m + y);}
vector <int> v[N];
void bfs()
{
    queue <int> q;
    q.push (sp);
    d[sp] = 1;
    while (q.size ())
    {
        int u = q.front (); q.pop ();
        if (u == tp) return;
        for (int j : v[u])
        {
            if (d[j]) continue;
            d[j] = d[u] + 1;
            q.push (j);
        }
    }
}
signed main()
{
    cin.tie (0), cout.tie (0);
    ios :: sync_with_stdio (false);
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n * m; i++)
                v[i].clear (), d[i] = 0;
        getline (cin, s[1]);
        for (int i = 1; i <= n * 4 + 3; i++)
            getline (cin, s[i]), s[i] = " " + s[i];
        // for (int i = 1; i <= n * 4 + 3; i++)
        //     cout << s[i] << "\n";
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (j % 2)
                {
                    int cx = (i - 1) * 4 + 3, cy = 12 * (j >> 1) + 5;
                    // cout << i << " " << j << " " << cx << " " << cy << "\n";
                    if (s[cx][cy] == 'S') sp = Hash (i, j);
                    if (s[cx][cy] == 'T') tp = Hash (i, j);
                    if (s[cx - 1][cy - 3] == ' ') v[Hash (i, j)].push_back (Hash (i - 1, j - 1));
                    if (s[cx - 1][cy + 3] == ' ') v[Hash (i, j)].push_back (Hash (i - 1, j + 1));
                    if (s[cx - 2][cy] == ' ') v[Hash (i, j)].push_back (Hash (i - 1, j));
                    if (s[cx + 1][cy - 3] == ' ') v[Hash (i, j)].push_back (Hash (i, j - 1));
                    if (s[cx + 1][cy + 3] == ' ') v[Hash (i, j)].push_back (Hash (i, j + 1));
                    if (s[cx + 2][cy] == ' ') v[Hash (i, j)].push_back (Hash (i + 1, j));
                }
                else
                {
                    int cx = (i - 1) * 4 + 5, cy = 12 * (j >> 1) - 1;
                    if (s[cx][cy] == 'S') sp = Hash (i, j);
                    if (s[cx][cy] == 'T') tp = Hash (i, j);
                    if (s[cx - 1][cy - 3] == ' ') v[Hash (i, j)].push_back (Hash (i, j - 1));
                    if (s[cx - 1][cy + 3] == ' ') v[Hash (i, j)].push_back (Hash (i, j + 1));
                    if (s[cx - 2][cy] == ' ') v[Hash (i, j)].push_back (Hash (i - 1, j));
                    if (s[cx + 1][cy - 3] == ' ') v[Hash (i, j)].push_back (Hash (i + 1, j - 1));
                    if (s[cx + 1][cy + 3] == ' ') v[Hash (i, j)].push_back (Hash (i + 1, j + 1));
                    if (s[cx + 2][cy] == ' ') v[Hash (i, j)].push_back (Hash (i + 1, j));
                }
            }
        // for (int i = 1; i <= n * m; i++)
        //     for (int j : v[i]) cout << i << " " << j << "\n";
        bfs ();
        if (d[tp]) cout << d[tp] << "\n";
        else cout << "-1\n";
    }
    return 0;
}//Ciallo~(∠·ω<)⌒☆