解题思路

1. 数字分层

   • 将三角形网格中的数字按层划分，第 k 层的数字范围是 3k(k-1)+1 到 3k(k+1)。
   • 例如：第1层是 1，第2层是 2~7，第3层是 8~19，依此类推。

2. 定位数字所在层

   • 给定数字 x，找到满足 3k(k-1)+1 ≤ x ≤ 3k(k+1) 的层数 k。

3. 计算最短路径

   • 设数字 M 和 N 分别位于层 m_line 和 n_line。
   • 最短路径长度 = 层数差 + 左斜方向偏移差 + 右斜方向偏移差。
     • 层数差：|n_line - m_line|（垂直移动步数）。
     • 左斜偏移差：|(N在左斜方向的位置) - (M在左斜方向的位置)|。
     • 右斜偏移差：|(N在右斜方向的位置) - (M在右斜方向的位置)|。

关键点：通过分层和方向偏移的差值，直接计算最短路径，无需复杂搜索。

 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
//#define DEBUG
 
using namespace std;
 
const int N = 1e9;
const int N1 = 32000;
int start[N1], dest[N1];
 
void init()
{
        int t = 1;
        for(int i=1, j=1; ;i+=2, j++)
        {
            start[j] = t;
            dest[j] = (t += i) - 1;
            if(t > N) {
#ifdef DEBUG
                printf("N2=%d\n", j);
#endif
                break;
            }
        }
}
 
int find(int x)
{
    for(int i=1; ;i++)
        if(x <= dest[i])
            return i;
}
 
int main()
{
    init();
 
    int m, n, ans;
    while(scanf("%d%d", &m, &n)==2) {
        int mline = find(m);
        int nline = find(n);
        ans = abs(nline - mline) +
                abs((n - start[nline]) / 2 - (m-start[mline]) / 2) +
                abs((dest[nline] - n) / 2 - (dest[mline] - m) / 2);
 
        printf("%d\n", ans);
    }
 
    return 0;
}
 

题意分析

一个个点在三角形中按顺序排列 输入两个点m，n，要求找出从m到n的最短路径。 移动规则如下：一个点到另一个点，只能通过两点之间的边移动。

解题思路

该题最重要的点就是搞懂点移动的规则。当点为1时，只能向下移动，当点为平方数时，不能向右和上方移动，当点为平方数+1时，不能向左和上方移动，中间的点可以左右移动，不难从图中看出，一行中的偶数列可以向上移动，奇数列可以向下移动。根据此规则，我们需要计算出一个点的行数和列数。 假设一个数为n，行数$k = pow（n，0.5）$向上取整。 列数$i = n - pow((k-1),2)$ 题目为最小路径问题，不难想到bfs，但是题目数据量大，为了缩短运行时间，采用双向bfs。

标程

```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <map>      
#include <string>
#include <cstdlib>  

using namespace std;

// 整数二分法计算k=ceil(sqrt(x))
int int_ceil_sqrt(int x) {
    if (x <= 1) return x;
    int left = 1, right = x;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (mid * mid < x) left = mid + 1;
        else right = mid;
    }
    return left;
}

// 计算相邻节点
vector<string> get_directions(int x) {
    vector<string> dirs;
    if (x == 1) {
        dirs.push_back("bottom");
        return dirs;
    }
    int k = int_ceil_sqrt(x);
    int layer_start = (k-1)*(k-1);
    int i = x - layer_start;
    
    if (i > 1) dirs.push_back("left");
    if (x < k*k) dirs.push_back("right");
    
    if (i % 2 != 0)
        dirs.push_back("bottom");
    else
        dirs.push_back("top");
        
    return dirs;
}

// 移动计算
int move(int x, const string& dir) {
    int k = int_ceil_sqrt(x);
    int layer_start = (k-1)*(k-1);
    int i = x - layer_start;
    
    if (dir == "left") return x-1;
    if (dir == "right") return x+1;
    if (dir == "top") return (k-2)*(k-2) + (i-1);
    if (dir == "bottom") return k*k + (i+1);
    
    return -1;
}

// 双向BFS
int bidirectional_bfs(int start, int target) {
    if (start == target) return 0;
    
    queue<int> q1, q2;
    map<int, int> dist1, dist2;  
    
    q1.push(start); dist1[start] = 0;
    q2.push(target); dist2[target] = 0;
    
    while (!q1.empty() && !q2.empty()) {
        if (q1.size() <= q2.size()) {
            for (int sz = q1.size(); sz > 0; --sz) {
                int u = q1.front(); q1.pop();
                vector<string> dirs = get_directions(u);
                for (vector<string>::iterator it = dirs.begin(); it != dirs.end(); ++it) {
                    string dir = *it;
                    int v = move(u, dir);
                    if (v <= 0) continue;
                    
                    if (dist2.find(v) != dist2.end())
                        return dist1[u] + 1 + dist2[v];
                        
                    if (dist1.find(v) == dist1.end()) {
                        dist1[v] = dist1[u] + 1;
                        q1.push(v);
                    }
                }
            }
        } else {
            for (int sz = q2.size(); sz > 0; --sz) {
                int u = q2.front(); q2.pop();
                vector<string> dirs = get_directions(u);
                for (vector<string>::iterator it = dirs.begin(); it != dirs.end(); ++it) {
                    string dir = *it;
                    int v = move(u, dir);
                    if (v <= 0) continue;
                    
                    if (dist1.find(v) != dist1.end())
                        return dist2[u] + 1 + dist1[v];
                        
                    if (dist2.find(v) == dist2.end()) {
                        dist2[v] = dist2[u] + 1;
                        q2.push(v);
                    }
                }
            }
        }
    }
    return -1;
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << bidirectional_bfs(m, n) << endl;
    return 0;
}