bfs | memoization
\nclass Solution {\n    public int minimumMoves(int[][] grid) {\n        Queue<int[]> q=new LinkedList<>();\n        q.add(new int[]{0,0,0,1,0,0});\n        int
```\nclass Solution {\n    public int minimumMoves(int[][] grid) {\n        Queue<int[]> q=new LinkedList<>();\n        q.add(new int[]{0,0,0,1,0,0});\n        int n=grid.length;\n        boolean[][][] vis=new boolean[n][n][2];\n        while(!q.isEmpty()){\n            int[] cur=q.remove();\n            int position=cur[4];\n            // System.out.println(cur[0]+","+cur[1]+" | "+cur[2]+","+cur[3]+" "+(position==0?"horizontal":"vertical"));\n            if(vis[cur[2]][cur[3]][position]){\n                continue;\n            }\n            // System.out.println(cur[0]+","+cur[1]+" | "+cur[2]+","+cur[3]);\n            vis[cur[2]][cur[3]][position]=true;\n            if(cur[0]==n-1 && cur[1]==n-2 && cur[2]==n-1 && cur[3]==n-1){\n                return cur[5];\n            }\n            //horizontal\n            if(position==0){\n                if(cur[2]+1<n && grid[cur[2]+1][cur[3]-1]+grid[cur[2]+1][cur[3]]==0){\n                    q.add(new int[]{cur[0],cur[1],cur[2]+1,cur[3]-1,(position+1)%2,cur[5]+1});\n                }\n                if(cur[3]+1<n && grid[cur[2]][cur[3]+1]==0){\n                    q.add(new int[]{cur[2],cur[3],cur[2],cur[3]+1,position,cur[5]+1});\n                }\n                if(cur[0]+1<n && cur[2]+1<n && grid[cur[0]+1][cur[1]]+grid[cur[2]+1][cur[3]]==0){\n                    q.add(new int[]{cur[0]+1,cur[1],cur[2]+1,cur[3],position,cur[5]+1});\n                }\n            }\n            //vertical\n            else{\n                if(cur[3]+1<n && grid[cur[2]-1][cur[3]+1]+grid[cur[2]][cur[3]+1]==0){\n                    q.add(new int[]{cur[0],cur[1],cur[2]-1,cur[3]+1,(position+1)%2,cur[5]+1});\n                }\n                if(cur[2]+1<n && grid[cur[2]+1][cur[3]]==0){\n                    q.add(new int[]{cur[2],cur[3],cur[2]+1,cur[3],position,cur[5]+1});\n                }\n                if(cur[1]+1<n && cur[3]+1<n && grid[cur[0]][cur[1]+1]+grid[cur[2]][cur[3]+1]==0){\n                    q.add(new int[]{cur[0],cur[1]+1,cur[2],cur[3]+1,position,cur[5]+1});\n                }\n            }\n        }\n        return -1;\n    }\n    boolean isValid(int[] cur, int n){\n        return cur[0]<n && cur[2]<n && cur[1]<n && cur[3]<n;\n    }\n}\n```
['Breadth-First Search']