// Finds the Longest Path from source to destination

import java.io.*;
import java.util.*;

public class Solution {
    static int globalLongest = 0;
    static ArrayList<ArrayList<Integer>> LongestPath = new ArrayList<ArrayList<Integer>> ();

    static ArrayList<ArrayList<Integer>> longestPath(int[][] maze, int startX, int startY, int targetX, int targetY) {

        dfs(maze, startX, startY, targetX, targetY, 1, new ArrayList<ArrayList<Integer>>());
        return LongestPath;
    }

    static void dfs(int[][] maze, int x, int y, int targetX, int targetY, int longest, ArrayList<ArrayList<Integer>> path){
        maze[x][y] = 1;
        path.add(new ArrayList<Integer>(List.of(x,y)));

        if(x == targetX && y == targetY) {
            if(globalLongest < longest) {
                globalLongest = longest;
                LongestPath = (ArrayList<ArrayList<Integer>>) path.clone();
            }
            maze[x][y] = 0;
            path.remove(path.size()-1);
            return;
        }

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

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

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

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

        maze[x][y] = 0;
        path.remove(path.size()-1);
    }

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

        ArrayList<ArrayList<Integer>> LongestPath = longestPath(maze, 0, 1, 3, 5);
        System.out.println(LongestPath.size());
        for(int i = 0; i < LongestPath.size(); i++) {
            System.out.print("(" + LongestPath.get(i).get(0) + ", " + LongestPath.get(i).get(1) + ") -> ");
        }
    }
}