???? 题目
有一个 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); }}???? 类似题目
695. 岛屿的最大面积