Djkistra Algorithm
Intuition\nFirst thoght is of Dynamic programming.But it is very Compliacted because we have four directions to move so there is a possibility of cycle and if w
# Intuition\nFirst thoght is of Dynamic programming.But it is very Compliacted because we have four directions to move so there is a possibility of cycle and if we do dp we need to handle the cycle also. so think of graph algorithms.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nso the approach is using Djkistra algo. where we need to store three states i,j,move .move is  to check whether it is even or odd .\nto check even or odd i am taking xor with 1.and simply applying Djkistra Algorithm\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    int directions[][]={{1,0},{0,1},{-1,0},{0,-1}};\n    public int minTimeToReach(int[][] moveTime) {\n        int m=moveTime.length;\n        int n=moveTime[0].length;\n\n        int dis[][][]=new int [m][n][2];\n        for(int row[][]:dis){\n            for(int r[]:row){\n                Arrays.fill(r,Integer.MAX_VALUE);\n            }\n        }\n        dis[0][0][0]=0;\n        PriorityQueue<int[]> pq =new PriorityQueue<>(Comparator.comparingInt(a->a[0]));\n        pq.offer(new int[]{0,0,0,0});\n        while(!pq.isEmpty()){\n            int nu[]=pq.poll();\n            int dist=nu[0];\n            int i=nu[1];\n            int j=nu[2];\n            int move=nu[3];\n            int cost=(move%2==0?true:false)?1:2;\n            for(int dir[]:directions){\n                int newi=i+dir[0];\n                int newj=j+dir[1];\n                int nextmove=(move ^1);\n                if(newi>=0 && newj>=0 && newi<m && newj<n && dis[newi][newj][nextmove]>Math.max((dis[i][j][move]+cost),moveTime[newi][newj]+cost)){\n                    dis[newi][newj][nextmove]=Math.max((dis[i][j][move]+cost),moveTime[newi][newj]+cost);\n\n                    pq.offer(new int[]{dis[newi][newj][nextmove],newi,newj,nextmove});\n\n                }\n            }\n            \n        }\n        return Math.min(dis[m-1][n-1][0],dis[m-1][n-1][1]);\n    }\n}\n```
['Graph', 'Java']