Given an integer matrix, find the length of the longest path that have same values. The matrix has no boundary limits. (like, Google Maps - see edit for context)
From each cell, you can either move to two directions: horizontal or vertical. You may NOT move diagonally or move outside of the boundary.
nums = [
[1,1],
[5,5],
[5,5]
]
Return 4 ( Four 5's).
https://leetcode.com/discuss/interview-question/392780/Doordash-or-Phone-Screen-or-Longest-path-duplicate-numbers-within-a-Matrix思路： 这题是doordash的真题，重复的number， longest path，这题跟 Longest Increasing Path in a Matrix??不一样的是，他求的元素是相同的，不能用dp来算，longest increasing path, 每个元素都不同，而且有大小关系，只访问一次，所以关系是可以继承的，用cache保住是没有问题的，但是这个题目是一模一样的元素length有多少，那么你是无法cache住的，所以只能以每个点为起点，开始dfs，然后计算每个点的length最大；
package com.company.DoorDash;
import java.util.Arrays;
public class longestDuplicatePath_DoorDash {
public int findLongestDuplicatePath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int globalLongest = 1;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
boolean[][] visited = new boolean[m][n];
globalLongest = Math.max(globalLongest, dfs(matrix, visited, i, j, matrix[i][j]));
}
}
return globalLongest;
}
private int[][] dirs = new int[][]{{0,-1},{0,1},{1,0},{-1,0}};
private int dfs(int[][] matrix, boolean[][] visited, int x, int y, int target) {
int m = matrix.length;
int n = matrix[0].length;
int count = 1;
visited[x][y] = true;
for(int[] dir: dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if(0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny] && matrix[nx][ny] == target) {
count = Math.max(count, 1 + dfs(matrix, visited, nx, ny, target));
}
}
visited[x][y] = false;
return count;
}
public static void main(String[] args) {
longestDuplicatePath_DoorDash longestDuplicatePath_doorDash = new longestDuplicatePath_DoorDash();
int[][] nums = {{1,1},
{5,5},
{5,5}};
// expected length is: 4;
System.out.println("findLongestDuplicatePath is:" + longestDuplicatePath_doorDash.findLongestDuplicatePath(nums));
}
}
