在这里,我想使用dfs在2D数组中从左列到最右列中遍历,每个元素可以转到其右上元素或右元素或右下元素。我需要记录每条可能的路径。例如,我有:
1 2 3
4 5 6
7 8 9
然后,可能的路径将为123、126、153、156、159、423、426、453、456、459、486、489、753、756、756、759、786、786、789
现在我的想法很简单:
public int findSolution(int[][] array) {
List<List<Integer>> availablePaths = new ArrayList<List<Integer>>();
for (int i = 0; i < array.length; i++) {
List<Integer> tempList = new ArrayList<Integer>();
dfs(array, availablePaths, tempList, 0, i);
}
int res = 0;
int min = Integer.MAX_VALUE;
for (List<Integer> path : availablePaths) {
min = Integer.MAX_VALUE;
for (Integer cur : path) {
if (cur < min) {
min = cur;
}
}
if (min > res) {
res = min;
}
}
return res;
}
public void dfs(int[][] array, List<List<Integer>> availablePaths, List<Integer> tempList, int curCol, int curRow) {
if (tempList.size() == array[0].length) {
availablePaths.add(new ArrayList<Integer>(tempList));
return;
}
tempList.add(array[curRow][curCol]);
int startRow;
int endRow;
// Next Column
if (curRow == 0) {
startRow = 0;
endRow = curRow+1;
} else if (curRow == array.length-1) {
startRow = curRow - 1;
endRow = curRow;
} else {
startRow = curRow - 1;
endRow = curRow + 1;
}
for (int i = startRow; i <= endRow; i++) {
dfs(array, availablePaths, tempList, curCol + 1, i);
tempList.remove(tempList.size()-1);
}
}
但是,由于ArrayIndexOutOfBoundSexception,这是行不通的,所以我想我的代码有错误的想法。
有人可以提供解决这个问题的解决方案吗?
以下DFS实现解决了您的问题。我也添加了您的示例作为测试用例。基本上,我们在第一列的每个单元格上启动了一个新的DFS。在每个DFS调用中,只要当前单元格处于界限,我们就将其添加到列表中的当前路径中。如果当前单元格已经是最后一列,请添加列表中的路径中的路径中的最终结果。
dx,dy数组是实现3个可能的动作的简洁方法。
import java.util.ArrayList;
import java.util.List;
public class Solution {
private static int[] dx = {-1,0,1}, dy = {1,1,1};
public static List<List<Integer>> dfsForAllPaths(int[][] grid) {
List<List<Integer>> res = new ArrayList<>();
if(grid == null) {
return res;
}
for(int i = 0; i < grid[0].length; i++) {
dfsHelper(grid, i, 0, res, new ArrayList<>());
}
return res;
}
private static void dfsHelper(int[][] grid, int x, int y, List<List<Integer>> res, List<Integer> list) {
if(!isInBound(grid, x, y)) {
return;
}
list.add(grid[x][y]);
if(y == grid[0].length - 1) {
res.add(new ArrayList<>(list));
}
for(int dir = 0; dir < 3; dir++) {
int newX = x + dx[dir], newY = y + dy[dir];
dfsHelper(grid, newX, newY, res, list);
}
list.remove(list.size() - 1);
}
private static boolean isInBound(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}
public static void main(String[] args) {
int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};
List<List<Integer>> res = dfsForAllPaths(grid);
for(int i = 0; i < res.size(); i++) {
System.out.println(res.get(i));
}
}
}