In this practice, you will implement a breadth-first search of a matrix.
- Clone the starter from the bottom of the page.
npm install
to install dependencies- Fill out code in bfs-path.js to solve the problem
- Uncomment the marked code and run
node bfs-path.js
to run local test cases npm test
to run the test specs
Given a matrix, start node, and end value, search the matrix from start node until you find the end value using a breadth-first search.
Return an array with all of the [row, col] coordinates (nodes) that the breadth-first-search will visit while traversing from the start node to the end value. If the end value is not found, return false.
Examples:
const matrix1 = [
[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]
];
bfsPath(matrix1, [ 0, 0 ], 16);
// returns an array of coordinates with no duplicates:
// [
// [ 0, 0 ], [ 1, 0 ],
// [ 0, 1 ], [ 2, 0 ],
// [ 1, 1 ], [ 0, 2 ],
// [ 3, 0 ], [ 2, 1 ],
// [ 1, 2 ], [ 0, 3 ],
// [ 3, 1 ], [ 2, 2 ],
// [ 1, 3 ], [ 3, 2 ],
// [ 2, 3 ], [ 3, 3 ]
// ]
// Note: The coordinates represent the following matrix values, in order:
// 1 5 2 9 6 3 13 10 7 4 14 11 8 15 12 16
// This information may be helpful for debugging purposes
bfsPath(matrix1, [ 2, 2 ], 17)
// returns false since end value is not included in the matrix
This function should accept a single node from the matrix, as well as the matrix
itself. The function should return an array containing all of the valid
neighbor nodes of that node, in [ row, col ]
format.
A valid neighbor is a node directly above, below, to the left and to the right of the node, and does NOT include diagonal neighbors.
Run the first set of local tests to confirm that your findNeighbors
function
is returning the correct array of nodes, and correctly accounts for nodes at the
edge or corners of the matrix.
This function should accept a matrix (two-dimensional array), a start node, and
an end value. The start node is in the [ row, col ]
format, and points to a
specific coordinate on the matrix itself.
The function should return an array of [ row, col ]
coordinates that represent
the path of the breadth-first search.
Run the second set of local tests to confirm that your bfsPath
function
is returning the correct path, and returns false
if the endValue
does not
exist within the array.# bfs-path-practice