PathItem.java

// Path tree item. 
class PathItem {
    // array row coord
    int x;
    // array col coord
    int y;
    // path length
    int len;
    // further path
    PathItem next;
}    

Rook.java

public class Rook {

    public static void main(String[] args) {
        // initialize target array
        int[][] a = {
            {5, 12, 7},
            {1, 4,  9}, 
            {3, 6,  2}    
        };        
        int n = 3;
        // create path length matrix/memoized storage
        PathItem[][] tmp = new PathItem[n][n];

        // find longest path by coords
        PathItem path = FindPath(tmp, a, 0, 1, n);

        // dump length matrix
        System.out.println("path length matrix:");
        for(int y=0; y<n; y++){
            System.out.printf("%d: ", y);
            for(int x=0; x<n; x++){
               if (tmp[y][x]!=null) {
                  System.out.printf("len:%d %s | ", tmp[y][x].len, tmp[y][x].next!=null);
               } else {
                  System.out.printf("?");
               }
            }
            System.out.printf("\n");
        }
        // dump path
        System.out.println("path:");
        while(path != null) {
            System.out.printf("(%d,%d) v:%d\n", path.x , path.y, a[path.y][path.x]);
            path = path.next;
        }
    }

    // recursive longest path search
    public static PathItem FindPath (PathItem[][] tmp, int[][] a, int x, int y, int n) {
        // already memoized?
        if (tmp[y][x] != null) {
            return tmp[y][x];
        }

        // seek max length path horizontally        
        int len = 0;
        PathItem path = null;
        for(int i=0; i<n; i++) {
            if (i!=x && a[y][i] > a[y][x]) {                           
               PathItem v = FindPath(tmp, a, i, y, n);
               if (v.len>len) {
                  len = v.len;
                  path = v;
               }                
            }            
        }

        // seek max length path vertically
        for(int j=0; j<n; j++) {
            if (j!=y && a[j][x] > a[y][x]) {            
               PathItem v = FindPath(tmp, a, x, j, n);
               if (v.len>len) {
                  len = v.len;
                  path = v;
               }                
            }            
        }
        
        // fill current cell max path
        PathItem pathItem = new PathItem();
        pathItem.x = x;
        pathItem.y = y;
        pathItem.len = len+1;
        pathItem.next = path;
        // memoize it
        tmp[y][x] = pathItem;
        return pathItem;

    }
}

javac Rook.java PathItem.java
java -cp . Rook