Ich weiß, dass viele Algorithmen zur Verfügung stehen, um den kürzesten Weg zwischen zwei Punkten in einem Graphen oder einem Gitter zu berechnen, z. B. die Breite zuerst, alle Paare (Floyd's), Dijkstra's.

Wie ich jedoch bemerkt habe, berechnen alle diese Algorithmen alle Pfade in diesem Diagramm oder Raster, nicht nur die zwischen den beiden Punkten, an denen wir interessiert sind.

MEINE FRAGE IST: Wenn ich ein Gitter habe, dh ein zweidimensionales Array, und ich daran interessiert bin, den kürzesten Weg zwischen zwei Punkten, z. B. P1 und P2, zu berechnen, und wenn Einschränkungen hinsichtlich der Art und Weise bestehen, in der ich mich auf dem Gitter bewegen kann (z. B. nur diagonal) , oder nur diagonal und aufwärts usw.), welcher Algorithmus kann das berechnen?

Bitte beachten Sie hier, dass Sie, wenn Sie eine Antwort haben, lieber den Namen des Algorithmus als den Algorithmus selbst posten möchten (natürlich noch besser, wenn Sie auch den Algorithmus posten). Zum Beispiel, ob es sich um den Algorithmus von Dijkstra oder Floyd oder was auch immer handelt.

Bitte helfen Sie mir, ich habe monatelang darüber nachgedacht!

Ok Leute, ich habe diesen Algorithmus auf TOPCODER.COM hier im Gitter gefunden. Du kannst dich nur (diagonal und nach oben) bewegen, aber ich kann nicht verstehen, welcher Algorithmus das ist. Könnte jemand das wissen?

#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);
}
};