幅優先、全ペア (フロイド)、ダイクストラのように、グラフまたはグリッド内の 2 点間の最短経路を計算するために多くのアルゴリズムが利用できることを知っています。
しかし、私が気づいたように、これらのアルゴリズムはすべて、関心のある 2 点間のパスだけでなく、そのグラフまたはグリッド内のすべてのパスを計算します。
私の質問は: グリッド、つまり 2 次元配列があり、P1 と P2 などの 2 点間の最短経路を計算することに関心があり、グリッド上を移動できる方法に制限がある場合 (たとえば、斜めのみ、または斜めと上向きのみなど)、どのアルゴリズムがこれを計算できますか?
回答がある場合は、アルゴリズム自体ではなくアルゴリズムの名前を投稿していただきたいことに注意してください (もちろん、アルゴリズムも投稿するとさらに良いでしょう)。たとえば、それがダイクストラのアルゴリズムであるか、フロイドのアルゴリズムであるか、またはその他のものであるかどうか。
私を助けてください、私はこれについて何ヶ月も考えてきました!
わかりました、TOPCODER.COM でこのアルゴリズムを見つけました。ここのグリッドでは、(斜め上に) しか移動できませんが、これがどのようなアルゴリズムなのか理解できません。
#include<iostream>
#include <cmath>
using namespace std;
inline int Calc(int x,int y)
{
if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
}
class SliverDistance
{
public:
int minSteps(int x1,int y1, int x2, int y2)
{
int ret=0;
if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
return ret+Calc(x2-x1,y2-y1);
}
};