/**
1. 怎么找递增路径? 怎么找最长的?
2. 搜索: 从起点集合中找一个点, bfs 按严格升序遍历所有情况,  返回达到的最远距离
3. 剪枝: 
    3.1 一个路径中a->b, a能到达b, 则a点能到达的最长路径必定大于b点能达到的, 所以应该把能到达的点都从起点集合中删除
*/

class Solution {

    static final int[] dx = {0, 0, 1, -1};
    static final int[] dy = {1, -1, 0, 0};

    class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix.length , m = matrix[0].length;
        boolean[][] notStart = new boolean[n][m];
        Queue<Node> queue = new LinkedList<>();
        int result = 1;
        for (int i = 0;  i < n ; i ++){
            for (int j = 0; j < m ; j++){
                if (notStart[i][j]) continue;
                result = Math.max(result, bfs(i, j, matrix, queue, notStart));
            }
        }
        return result;
    }

    private int bfs(int x, int y, int[][] matrix, Queue<Node> queue, boolean[][] notStart){
        queue.clear();
        Node start = new Node(x, y);
        int n = matrix.length , m = matrix[0].length, result = 1;
        int[][] dis = new int[matrix.length][matrix[0].length];   
        queue.offer(start);
        dis[x][y] = 1;
        while (!queue.isEmpty()){
            Node node = queue.poll();
            for (int i = 0 ; i < 4 ; i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
                if (dis[node.x][node.y] >= dis[nx][ny] && matrix[nx][ny] > matrix[node.x][node.y]){
                    dis[nx][ny] = dis[node.x][node.y] + 1;
                    result = Math.max(result, dis[nx][ny]);
                    notStart[nx][ny] = true;
                    queue.offer(new Node(nx, ny));
                }
            }
        }
        return result;
    }
}