Suche nach Ausnahmen in Zählinseln

Question

Wenn es um Matrix-Traversals und jede Art von Suche geht, finde ich, dass ich oft ein potenzielles Element validieren muss, um es entweder zu meiner Warteschlange hinzuzufügen oder zu rekursieren.

sagen wir an dieser Matrix freuen:

var matrixTest = [ 
     [1,1,0,0,0], 
     [1,1,0,0,0], 
     [0,0,1,0,0], 
     [0,0,0,1,1] 
] 

In diesem Fall bin ich Iterieren alle Artikel über und Durchführen einer BFS (Markierung als besucht), wenn ich einen 1.

Ich begegne habe eine Subroutine innerhalb meiner BFS-Funktion, die bei einer Koordinate r und c alle möglichen von ihr ausgehenden Pfade validiert (r + 1, r-1, c + 1, c-1).

Das Problem ist mit diesem Stück Code

if(!visitMap[r+1][c] && matrix[r+1][c] === 1) { 
     q.push([r+1, c]) 
    } 

visitMap eine Matrix I ist neben dem Algorithmus erstellt, um sicherzustellen, ich bin nicht einen Punkt Verarbeitung zweimal

Matrix wird die Eingangsmatrix

Es scheint jedoch, dass ich die Eingaben vor dem Test validieren muss, da JavaScript diesen Fehler verursacht

Ich nehme an, das bedeutet, dass mein "r + 1" -Ausdruck außerhalb der Grenzen der Matrix liegt und somit als undefiniert abläuft.

Es scheint äußerst mühsam, eine weitere Schicht von Wenn/Dann-Fluss hinzuzufügen, um die Grenzen von r + 1, r-1, c + 1, UND c-1 zu überprüfen.

Gibt es ein bestimmtes Codemuster, das Sie verwenden sollten, um dies häufig zu vermeiden?

ansonsten denke ich, der Codeblock wird wie folgt aussehen:

if (r+1 < matrix.length) { 

    if(!visitMap[r+1][c] && matrix[r+1][c] === 1) { 
     q.push([r+1, c]) 
     } 
    } 

Answer 1

Sie können versuchen, die Validierung von Grenzen und Ihren Zustand innerhalb einer Funktion wie diese zu verkapseln:

function pushToQueue(visitMap, matrix, r, c) { 
    if(typeof(matrix[r]) == "undefined" 
     || typeof(matrix[r][c]) == "undefined") { 
    return false; 
    } 
    return !visitMap[r][c] && matrix[r][c] === 1; 
} 

und Sie können es so nennen:

if(pushToQueue(visitMap, matrix, r + 1, c)) { 
    q.push([r+1, c]); 
} 

if(pushToQueue(visitMap, matrix, r - 1, c)) { 
    q.push([r-1, c]); 
} 
// etc ... 

Answer 2

Eine Lösung, die eine Funktion jedes Mal, wenn Sie würde verwenden versuchen, die Matrix in einer Position für den Zugriff auf die außerhalb der Grenzen zu sein, ist anfällig.

So würde matrix[r+1][c] === 1readMatrix(c, r+1) === 1 werden.

Dies sollte einen sehr geringen Einfluss auf die Gesamtleistung haben, selbst in Schuppen. (Wenn eine Verzweigungsprädiktor in dem letzten Maschinencode involviert ist, sollte es die richtige Vermutung der meiste Zeit machen, weil Sie in der Matrix der meisten Zeit sind.)

var matrix = [ 
 
    [1,1,0,0,0], 
 
    [1,1,0,0,0], 
 
    [0,0,1,0,0], 
 
    [0,0,0,1,1] 
 
]; 
 

 
function readMatrix(x, y) { 
 
    return matrix[y] && matrix[y][x] !== undefined ? matrix[y][x] : 0; 
 
} 
 

 
console.log(readMatrix(0, 0)); 
 
console.log(readMatrix(0, 7)); 
 
console.log(readMatrix(7, 0));