关于算法:DFS-相邻数字的最长路径

42次阅读

共计 1310 个字符，预计需要花费 4 分钟才能阅读完成。

有一个 M*N 的矩阵，每个元素的值取自 [1,2,3…MN] 的汇合，且互不雷同。设计一个程序，找出相邻数字的最长门路。
相邻数字的定义：在矩阵中上下左右地位相邻，且值相差为 1 的数字
例如，下图矩阵中相邻数字的最长链接门路为 1-2-3-4

9	8	7
5	6	4
1	2	3

dfs。并应用 visited 数组判断拜访与否来缩小不必要的循环。每次递归完结后，把以后最长的 list 赋值给 maxList。

如果某次失去的 list 长度 > 总数的一半，则它就是最长的门路。直径退出外层循环。在返回前对 list 进行排序。

public class Solution {ArrayList<Integer> maxList = new ArrayList<Integer>();
    ArrayList<Integer> list;
    boolean[][] visited;
    int xx, yy;
    int m, n;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    
    public List<Integer> calcMaxLen(int[][] grid) {
        if (grid == null || grid.length == 0 
                || grid[0].length == 0) {return new ArrayList<>();
        }
        
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        
        out: for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j]) {list = new ArrayList<>();
                    dfs(grid, i, j);
                    if (list.size() > m*n/2) {
                        maxList = list;
                        break out;
                    }
                    maxList = maxList.size() > list.size()? maxList: list;
                }
            }
        }
        
        Collections.sort(maxList, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {return o1-o2;}
        });
        return maxList;
    }
    
    private void dfs(int[][] grid, int i, int j) {visited[i][j] = true;
        list.add(grid[i][j]);
        
        for (int d = 0; d < 4; d++) {xx = i + dx[d];
            yy = j + dy[d];
            if (xx >=0 && xx < m && yy >=0 && yy < n
                    && !visited[xx][yy] && Math.abs(grid[i][j] - grid[xx][yy]) == 1) {dfs(grid, xx, yy);
            }
        }
    }
    
    public static void main(String[] args) {int[][] grid = {{9,8,7},
            {5,6,4},
            {1,2,3}};
        Solution s = new Solution();
        List<Integer> queue = s.calcMaxLen(grid);
        System.out.println(queue);
    }
}