Messy BFS
\n# Code\njava []\nclass Solution {\n\n    public int minimumMoves(int[][] grid) {\n        int n = grid.length;\n        Queue<int[]> q = new LinkedList<>();\n
\n# Code\n```java []\nclass Solution {\n\n    public int minimumMoves(int[][] grid) {\n        int n = grid.length;\n        Queue<int[]> q = new LinkedList<>();\n        int[] start = {0,0,0,1,0};\n        int[] end = {n-1,n-2,n-1,n-1,0};\n        Map<String,Boolean> vis = new HashMap<>();\n        q.add(start);\n        int dist = 0;\n        while(!q.isEmpty()){\n            int size = q.size();\n            for(int i = 0;i<size;i++){\n                int[] pos = q.poll();\n                String key = pos[0]+","+pos[1]+","+pos[2]+","+pos[3]+","+pos[4];\n                if(vis.containsKey(key))\n                    continue;\n                vis.put(key,true);\n                int taili = pos[0];\n                int tailj = pos[1];\n                int headi = pos[2];\n                int headj = pos[3];\n                int orient = pos[4];\n                if(Arrays.equals(pos,end))\n                    return dist;\n                // horizontal\n                if(orient == 0){\n                    //right\n                    if(headj+1<n && headi>=0 && headi<n && tailj+1<n && tailj+1>=0 && taili<n && taili>=0 && grid[headi][headj+1]!=1){\n                        q.add(new int[]{taili,tailj+1,headi,headj+1,0});\n                    }\n                    //down\n                    if(headi+1<n && taili+1<n && headj<n && tailj<n && taili+1>=0 && tailj>=0 && headj>=0 && tailj >=0 && grid[headi+1][headj]!=1 && grid[taili+1][tailj]!=1)\n                        q.add(new int[]{taili+1,tailj, headi+1,headj,0});\n                    //rotate clockwise\n                    if(taili>=0 && taili<n && tailj<n && tailj>=0 && headi+1>=0 && headi+1<n && headj-1>=0 && headj-1<n && grid[headi+1][headj]!=1 && grid[taili+1][tailj]!=1)\n                        q.add(new int[]{taili,tailj,headi+1,headj-1,1});\n                }\n                else{\n                    //right\n                    if(taili>=0 && taili<n && tailj+1>=0 && tailj+1<n && headi>=0 && headi<n && headj+1>=0 && headj+1<n &&  grid[headi][headj+1]!=1 && grid[taili][tailj+1]!=1)\n                        q.add(new int[]{taili,tailj+1,headi,headj+1,1});\n                    //down\n                    if(taili+1>=0 && taili+1<n && tailj>=0 && tailj<n && headi+1<n && headi+1>=0 && headj>=0 && headj<n && grid[headi+1][headj]!=1)\n                        q.add(new int[]{taili+1,tailj,headi+1,headj,1});\n                    //rotate anticlockwise\n                    if(tailj+1<n && taili >=0 && tailj+1 >=0 && taili<n && headj+1<n && headi-1>=0 && grid[taili][tailj+1]!=1 && grid[headi][headj+1]!=1)\n                        q.add(new int[]{taili,tailj,headi-1,headj+1,0});\n                }\n            \n            } \n            dist++;\n        }\n        return -1;\n    }\n}\n```
['Breadth-First Search', 'Java']