[DFS] 近接数の最長経路

問題

M*N行列があり、各要素の値は集合の[1,2,3.....MN]の集合から取り出され、互いに同一ではありません。隣接する数の最長経路を求めるプログラムを設計しなさい。隣接数の定義： 行列の上下左右の位置で互いに隣接し、値が1だけ異なる数。例えば、次の行列における隣接数の最長連結経路は1-2-3-4です。

解析

dfs.であり、不要なループを減らすために、訪問されたかどうかを判断するために訪問された配列を使用します。各再帰の最後に、現在の最長リストをmaxListに代入します。

ある時点で得られたリストの長さが全体の半分以上であれば、それが最長経路。Diameterは外側ループを抜けます。戻る前にリストをソートします。

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);
 }
}