Простейшая идея - рекурсивно попробовать все возможные пути, не пересекающиеся с пересечением, и каждый раз, когда такой путь попадает в нижний правый угол, проверьте, равна ли эта длина числу всех ячеек.
Здесь идет очень наивная [и, следовательно, медленная и потребляющая память] реализация в js (судя по вашему профилю, который вы знаете js), просто чтобы указать алгоритм формальным, недвусмысленным образом. Вы заинтересованы в «Хорошо, давайте сделаем это!» часть, до того лишь некоторые помощники, чтобы сделать этот пример на самом деле исполняемым:
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;
}
Наверняка вы хотите, чтобы представлять позиции по-разному, и для больших «матриц» вы должны избавиться от «неправильных путей» как можно скорее. , но надеюсь, что вы начнете где-то.