Hãy xem xét bài toán backtracing sau:Trên lưới 2 chiều, có 4 loại hình vuông -
-
1 đại diện cho hình vuông bắt đầu. Có chính xác một ô vuông bắt đầu.
-
2 đại diện cho hình vuông kết thúc. Có đúng một ô vuông kết thúc.
-
0 đại diện cho các ô trống mà chúng ta có thể đi qua.
-
−1 đại diện cho những chướng ngại vật mà chúng ta không thể vượt qua.
Chúng tôi được yêu cầu viết một hàm trả về số bước đi 4 hướng từ hình vuông bắt đầu đến hình vuông kết thúc, đi qua mọi hình vuông không chướng ngại vật chính xác một lần.
Ví dụ
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));
Giải thích
-
Chúng tôi thiết lập các biến để hỗ trợ lặp lại bốn hướng khi đi ngang qua lưới, đếm các số 0 trong ma trận để cho phép kiểm tra mức độ phù hợp khi đạt đến điều kiện cơ bản của đệ quy
-
Sau đó, chúng tôi thiết lập chức năng backtrack DFS (Depth First Search) để đánh dấu lưới có −1 trên đường dẫn hiện hoạt và để kiểm tra độ dài đường dẫn khi đến ô kết thúc
-
Và cuối cùng, chúng tôi khởi chạy DFS từ ô bắt đầu để đếm tất cả các đường dẫn đầy đủ và trả về số lượng
Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
2