dfs_example.java

import java.io.*;

public class Solution {
    static int globalLongest = 0;
    static int steps = 0;
    static int longestPath(int[][] maze, int startX, int startY, int targetX, int targetY) {
        dfs(maze, startX, startY, targetX, targetY, 1);
        return globalLongest;
    }

    static void dfs(int[][] maze, int x, int y, int targetX, int targetY, int longest){
        System.out.println("dfs loop:" + steps + ", x: " + x + ", y: " + y);
        steps++;
        maze[x][y] = 1;

        if(x == targetX && y == targetY) {
            if(globalLongest < longest) {
                globalLongest = longest;
            }
            maze[x][y] = 0;
            return;
        }

        if(x + 1 <  maze.length && maze[x+1][y] == 0)
            dfs(maze, x+1, y,  targetX, targetY, longest + 1);

        if(x - 1 >=  0 && maze[x-1][y] == 0)
            dfs(maze, x-1, y,  targetX, targetY, longest + 1);

        if(y + 1 <  maze[0].length && maze[x][y+1] == 0)
            dfs(maze, x, y+1,  targetX, targetY, longest + 1);

        if(y - 1 >=  0 && maze[x][y - 1] == 0)
            dfs(maze, x, y-1,  targetX, targetY, longest + 1);

        maze[x][y] = 0;
    }

    public static void main(String[] args) {
        int[][] maze = new int[5][7];
        maze[0] = new int[]{0,0,0,0,0,0,0};
        maze[1] = new int[]{0,1,0,0,1,0,0};
        maze[2] = new int[]{1,0,0,1,0,0,0};
        maze[3] = new int[]{0,0,0,0,0,0,0};
        maze[4] = new int[]{0,1,0,0,0,1,0};

        System.out.println(longestPath(maze, 0, 1, 3, 5));
    }
}