다음 역추적 문제를 고려하십시오. 2차원 격자에는 4가지 유형의 정사각형이 있습니다. -
-
1은 시작 사각형을 나타냅니다. 시작 사각형은 정확히 하나입니다.
-
2는 끝 사각형을 나타냅니다. 정확히 하나의 끝 사각형이 있습니다.
-
0은 우리가 걸을 수 있는 빈 사각형을 나타냅니다.
-
−1은 우리가 걸을 수 없는 장애물을 나타냅니다.
시작 사각형에서 끝 사각형까지의 4방향 걷기 횟수를 반환하는 함수를 작성해야 합니다. 이 함수는 모든 장애물이 아닌 사각형을 정확히 한 번만 지나갑니다.
예시
const arr = [
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
];
const uniquePaths = (arr, count = 0) => {
const dy = [1,−1,0,0], dx = [0,0,1,−1];
const m = arr.length, n = arr[0].length;
const totalZeroes = arr.map(row => row.filter(num => num ===
0).length).reduce((totalZeroes,nextRowZeroes) => totalZeroes +
nextRowZeroes, 0);
const depthFirstSearch = (i, j, covered) => {
if (arr[i][j] === 2){
if (covered === totalZeroes + 1) count++;
return;
};
for (let k = 0; k < 4; k++)
if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n
&& arr[i+dy[k]][j+dx[k]] !== −1 ){
arr[i][j] = −1;
depthFirstSearch(i+dy[k],j+dx[k],covered+1);
arr[i][j] = 0;
}
return;
};
for (let row = 0; row < m; row++)
for (let col = 0; col < n; col++)
if (arr[row][col] === 1){
arr[row][col] = −1;
depthFirstSearch(row,col,0);
break;
}
return count;
};
console.log(uniquePaths(arr)); 설명
-
그리드를 순회할 때 4방향 반복을 용이하게 하는 변수를 설정하고, 재귀의 기본 조건에 도달했을 때 적용 범위를 확인할 수 있도록 행렬에서 0을 계산합니다.
-
그런 다음 활성 경로에서 그리드를 -1로 표시하고 완료 셀에 도달할 때 경로 길이를 확인하기 위해 DFS(Depth First Search) 역추적 기능을 설정합니다.
-
마지막으로 시작 셀에서 DFS를 시작하여 모든 전체 경로를 계산하고 카운트를 반환합니다.
출력
콘솔의 출력은 -
2