C++での行列の2点間のすべての可能なパス

Question

NxM平面が与えられた場合、右、下、斜めの3つの点（右下、315°）で2点間の可能なすべてのパスを見つけます。

私はこの問題を抱えています。私はそれを2つの方法で解決しなければならない：再帰的かつ反復的。反復的に私はアイデアを持っていますが、実装方法はわかりません。

私のアイデアの説明は：

（Google翻訳）です。私たちはN列の幅とM列の高さのボードに直面しています。点（x1、y1）から別の点（x2、y2）に到達しなければならないので、（xi、yj）はNまたはMより大きくすることはできません。移動の制限は、右側（1）、斜め下側（2）、下側（3）にしか移動できないということです。これらの動きを考えると、私たちは左または上に行くことができないので、x1はx2より小さくなければならず、y1はy2より大きくなければなりません。 アルゴリズムは最初のポイント（x1、y1）から開始し、各移動に1つの3つの「子」を作成します。 右（x1 + 1） 対角線（x1 + 1、y1-1） 下-1） 各子供が受け入れる条件は、x1 < = N、y1 < = M、x1 < = x2、y1> = y2であるとする。

反復は、受け入れられた各子からさらに3人の子供（1回につき1つ）を作成しようとするものです。

この繰り返しは、各子の（x1、y1）が（x2、y2）に等しいと結論づけられます。

ありがとうございます。

Answer 1

反復アプローチする必要があります： これは、あなたがいないの追跡を意味し、メモ化によって解決することができます。我々は最初にソースセル（SX、SY）から開始 、それに到達する唯一の方法があり、従って

：擬似コード最初 M[x][y] = 0 , for all x,y. b/w sx, dx and sy,dy respecitevly

行列M

に特定の細胞に到達するための方法

sx,sy // source cell 
dx,dy // destination cell 
M[sx][sy] = 1 ; 
for row x between sx, dx : 
    for column y between sx, dy: 
    if y-1 >= sy: 
      M[x][y] += M[x][y-1] // coming to x,y from left cell 
    if x-1 >= sx: 
      M[x][y] += M[x][y-1] // coming to x,y from top cell 
    if x-1 >= sx && y-1 >= sy: 
      M[x][y] += M[x-1][y-1] // coming from diagonal left cell. 

回答はM [dx] [dy]になります。

再帰的アプローチ： は同じ考えのように反復アプローチで行く、同じことが同様に再帰的に実施することができる。

Initially M[x][y] == -1: for all x b/w sx and dx , for all y b/w sy and dy 

path(row, col) 
if row == dx && col == dy: 
    return 1 
if M[x][y] != -1: return M[x][y] // this means result for this is already calculated 
M[x][y] = 0      
if col+1 <= dy: 
     M[row][col] += path(row, col+1) // going right 
if row+1 <= dx: 
     M[row][col] += path (row+1, col) // going down 
if row+1 <= dx && col+1 <= dy: 
     M[row][col] += path(row+1, col+1) // going diagonally right 

return M[row][col] 

答えるM [SX] [SY]

Answer 2

簡単な再帰的解決策は、各再帰呼び出しで新しい子を作成することです。

int foundSolutions = 0; 
boolean pathExistsBetweenPoints(Point source, Point target, List<Point> previousPoints) { 
    //Check if we're there yet 
    if(source.x == target.x && source.y == target.y) { 
     foundSolutions++; 
     //Here you can display previousPoints if you want a possible solution 
     return true; 
    } 
    if(source.x > N || source.y > M || source.x > target.x || source.y > target.y) { 
     return false; //This trail is out of bounds 
    } 
    //Add this point to the list of points 
    List<Point> newPoints = previousPoints.add(source); 
    //Get the childpoints 
    Point rightPoint = new Point(source.x, source.y + 1); 
    Point diagonalPoint = new Point(source.x + 1, source.y + 1); 
    Point downPoint = new Point(source.x + 1, source.y); 
    //Check if any of the childs can reach the target 
    boolean validPath = pathExistsBetweenPoints(rightPoint, target, previousPoints); 
    validPath = validPath || pathExistsBetweenPoints(diagonalPoint, target, previousPoints); 
    validPath = validPath || pathExistsBetweenPoints(downPoint, target, previousPoints); 
    return validPath; 
} 

私はC++の構文に慣れていないんだけど、これはかなり翻訳可能