jtcgen
BAN USERpublic static boolean hasPath(int[][] m) {
// Assuming m has at least one row
boolean[][] visited = initVisited(m.length, m[0].length);
return hasPath(m, 0, 0, visited);
}
private static boolean[][] initVisited(int r, int c) {
boolean[][] visited = new boolean[r][c];
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
visited[i][j] = false;
return visited;
}
private static boolean hasPath(int[][] m, int r, int c, boolean[][] visited) {
if (r == m.length - 1 && c == m[0].length - 1) return true;
else if (visited[r][c]) return false;
final int value = m[r][c];
final boolean right = c < m[0].length-1 && m[r][c+1] != value ? hasPath(m, r, c+1, visited) : false;
final boolean bottom = r < m.length-1 && m[r+1][c] != value ? hasPath(m, r+1, c, visited) : false;
visited[r][c] = !right && !bottom;
return right || bottom;
}
- jtcgen April 05, 2018