Max Min Path

Quetion:

给一个matrix。对于所有从左上到右下的path，找出每一条path的min值。输出所有min值的max。

Analysis

• 用DFS遍历所有edge。
• 对于这道题来说，不记录visited的点，每次只往下或者右走，就可以保证：
  • 遍历所有的path（普通DFS只遍历vertex和edge）
  • 不会死循环（因为每次只忘右或者下走）
• max用一个global的变量更新。
• min作为parameter path到下一个点去就可以记录每条path的local min

DFS Pesudo code

DFS (graph G, start vertex v)
    Mark v as explored
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as explored then
            recursively call DFS(G,w)

Code

public class MaxMinPath {
    private int maxMin = Integer.MIN_VALUE;

    public int Solution(int[][] mat){
            if(mat.length==0 || mat[0].length==0) return maxMin;
            dfs(mat, 0, 0, Integer.MAX_VALUE);
            return maxMin;
    }

    private void dfs(int[][] mat, int i, int j, int minSofar){
            int M = mat.length, N = mat[0].length;
            //base case: out of bound (need to take care out of bounds first)
            if(i==M || j==N) return;
            //if not out of bound, update local minimum
            minSofar = Math.min(minSofar, mat[i][j]);
            //if reach last position, update maximum
            if(i==M-1 && j==N-1) {maxMin = Math.max(minSofar, maxMin);}        
            //explore down and right vertexes
            dfs(mat, i+1, j, minSofar);
            dfs(mat, i, j+1, minSofar);
    }
}

Question

• 遍历所有edge和遍历所有path感觉不是一件事？