mXn行列のすべての可能な一意のパスを見つける

Question

mXn行列の左上のほとんどのセルから右下のほとんどのセルに到達するためのすべての可能なパスを見つけるのを助けてください。

以下

が制限され、

1. はすでに訪問されているセルを訪問することはできません。
2. 出口に達する前にすべてのセル、つまり右下のほとんどのセルにアクセスする必要があります。

ロジックはほとんど試してみましたが、すべてのパスを取得できませんでした。ありがとう

Answer 1

最も簡単な考え方は、可能なすべての非自己交差パスを再帰的に試行し、そのパスが右下隅に当たるたびに長さがすべてのセルの数に等しいかどうかを確認することです。

ここでは、アルゴリズムを正式な、明白な方法で指すように、jsで（あなたはjsを知っているあなたのプロフィールによって判断すると）非常に素朴な[ゆえに遅く、メモリを消費する]あなたは "OK、これをやりましょう！"に興味があります。この例では、実際に実行可能にする唯一のいくつかのヘルパーになる前の部分は、：確かに

function paths(M,N) { 
    // is given pos present in list of poss?                                                          
    var pos_member = function(pos,poss) { 
     for(var i=0;i<poss.length;i++) 
      if(pos[0]==poss[i][0] && pos[1]==poss[i][1]) 
       return true; 
     return false; 
    }; 
    // all positions present in poss1 and not in poss2:                                                       
    var positions_diff = function(poss1,poss2) { 
     var poss_d = []; 
     for(var i=0;i<poss1.length;i++) 
      if(pos_member(poss1[i],poss2)==false) 
       poss_d.unshift(poss1[i]); 
     return poss_d; 
    }; 
    // where can you go from [x,y] ?                                                            
    var all_next_positions = function([x,y]) { 
     var poss = []; 
     // assuming no diagonal moves are allowed;                                                        
     // otherwise add 4 more next possible positions.                                                       
     if(x > 0) poss.unshift([x-1,y]); 
     if(x < M-1) poss.unshift([x+1,y]); 
     if(y > 0) poss.unshift([x,y-1]); 
     if(y < N-1) poss.unshift([x,y+1]); 
     return poss; 
    }; 

    //////// OK, let's do this! //////////////////////////////////                                                    
    var pending = [ [[0,0]] ]; // pending partial paths (looks like an owl statring at you, doesn't it?)                                           
    var results = []; // corect paths found so far                                                        

    while(pending.length>0) { 
     var current = pending.shift(); 
     var last_pos = current[0]; 
     if(last_pos[0]==M-1 && last_pos[1]==N-1) { 
      /// it reaached the goal, but did it visit all the cells?                                                   
      if(current.length == M*N) /// yes it did, so keep it.                                                    
       results.unshift(current); 
     } else { 
      /// keep going...                                                             
      var next_poss = positions_diff(all_next_positions(last_pos), current); 
      for(var i=0;i<next_poss.length;i++) { 
       var candidate = current.slice(0); /// clone, because call by reference is evil.                                             
       candidate.unshift(next_poss[i]); 
       pending.unshift(candidate); 
      } 
     } 
    } 
    return results; 
} 

あなたは異なった位置を表現したい、そしてより大きな「行列」のためにあなたはできるだけ早く、「間違ったパス」を取り除く必要があるだろう。しかし、これがあなたのどこかで始まることを願っています。