- Make a 2D array
boolean[][] visited
designating the points that you have visited; set all elements tofalse
- Go through each point in two nested loops
- For each point where
visited[r][c]
isfalse
, go into a DFS which you can implement recursively - Inside the recursive DFS call check if the point is your destination; if yes, return
true
- If the point has the correct color, explore its neighbors (up to four) in four directions
- If a neighbor has the right color, mark it as visited, and make a recursive call
- If a recursive call returns
true
, return true - Otherwise, continue exploring other neighbors
- Once you are done exploring neighbors, return
false
.
How to use DFS on an array
-
15-06-2023 - |
Pregunta
I have a 1 dimensional list of values, it looks like this "int[] values'". I beleive I have converted it to a 2d list like this :
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
board[i][j] = values[i * 4 + j];
}
}
The board is the new 2 dimensional list of values. On the board there are numbers. A 0 means an empty space, a 1 is a green, a 2 is a blue, and a 3 is a red. How would I use depth first search to find a completed path of a certain color?
Solución
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow