BFS with composite encoded key for visited
Intuition\nBecause this is a grid, edge weights are equal,\nso we can use BFS instead of UCS or A.\n\nA BFS search can be done from the box to the target,\nbut 
# Intuition\nBecause this is a grid, edge weights are equal,\nso we can use BFS instead of UCS or A*.\n\nA BFS search can be done from the box to the target,\nbut each move of the box must have a free space\non the opposite side of move,\nand that free space must be reachable by S at its current position.\n\n\n# Approach\nI used BFS to perform a search from the box B to the target T, checking at each move that S could get to the free space needed for the push.\n\nOne important detail was to use a composite key for the visited data structure which is used to avoid never ending cycles of actions.  The composite key is composed of the box position and the direction of its motion.\n\nAnother detail of the BFS search is to enqueu the box position and the person position.\n\n\n# Complexity\n- Time complexity:\n$$O((m*n)^2)$$ in the worst case where m and n are the dimensions of the grid.\nThe extra factor of m*n is due to needing to check that the push position is reachable by the person.\n\n- Space complexity:\n$$O(m*n)$$\n\n# Code\n```\nclass Solution {\n\n    protected static int[][] offsets = new int[4][];\n    static {\n        offsets[0] = new int[]{0, 1};\n        offsets[1] = new int[]{0, -1};\n        offsets[2] = new int[]{-1, 0};\n        offsets[3] = new int[]{1, 0};\n    }\n\n    public int minPushBox(char[][] grid) {\n\n        /*\n        m x n grid of characters grid where each element \n        is a wall, floor, or box.\n\n        only the box moves are counted.\n\n        Because this is a grid, edge weights are equal,\n        so we can use BFS instead of UCS or A*.\n\n        BFS of the box to the target,\n            but each move of the box must have a free space\n            on opposite side of move,\n            and that free space must be reachable by S at its current position.\n\n        A box needs to be able to revisit a cell, so the\n            visited array which helps constrain repeated visits\n            to a cell, needs to have a key that is a composite key\n            of position and other information unique to the action.\n            We can use the box position and push direction as a composite\n            key, or alternatively, we could\n            use the push position and direction as a composite key.\n            \n            The box position value range is [0, m*n] where m and n are\n            have max value constraints of 20.\n            The box position range = [0, 400] so position needs 9 bits.\n            The direction needs 2 numbers which are both 2 bits.\n            So, the composite index uses 13 bits of an integer.\n            \n            Note, that the visited state should not be set until all checks that\n            the box is pushable by person are done, so that we are only\n            restricting revisits of truly visitable states.\n\n        The runtime complexity at worst is O((n*m)^2).\n        The space complexity is O(n*m).\n        */\n\n        return useBFS(grid);\n    }\n\n    /*\n    9 bits for box position,\n    2 bits for offset[0]\n    2 bits for offset[2]\n    */\n    protected int encodeCompositeIndex(int idx, int[] offset) {\n        int a = idx;\n        // offset range is -1 to 1, so we add 1 to make range [0,2]\n        a |= ((offset[0]+1) << 9);\n        a |= ((offset[1]+1) << 11);\n        return a;\n    }\n\n    protected int useBFS(char[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n\n        int bIdx = -1;\n        int sIdx = -1;\n        int tIdx = -1;\n        // find the box, person, and target\n        int r, c;\n        char cell;\n        for (r = 0; r < m; ++r) {\n            for (c = 0; c < n; ++c) {\n                cell = grid[r][c];\n                switch(cell) {\n                    case \'B\':\n                        bIdx = (r*n) + c;\n                        break;\n                    case \'S\':\n                        sIdx = (r*n) + c;\n                        break;\n                    case \'T\':\n                        tIdx = (r*n) + c;\n                        break;\n                    default:\n                        break;\n                }\n            }\n        }\n        assert(sIdx > -1);\n        assert(bIdx > -1);\n        assert(tIdx > -1);\n\n        // index is composite key of box position and direction of motion\n        Set<Integer> visited = new HashSet<>();\n\n        int r2, c2, bIdx2, sIdx2;\n        char cell2;\n        int bIdx1, sIdx1;\n\n        Queue<Integer> q = new ArrayDeque<>();\n        Queue<Integer> qS = new ArrayDeque<>();\n        q.offer(bIdx);\n        qS.offer(sIdx);\n\n        int len = -1;\n        while (!q.isEmpty()) {\n            ++len;\n            \n            int qSz = q.size();\n\n            while (qSz > 0) {\n                --qSz;\n\n                bIdx1 = q.poll();\n                sIdx1 = qS.poll();\n\n                r = bIdx1 / n;\n                c = bIdx1 % n;\n\n                if (grid[r][c] == \'T\') return len;\n\n                // candidate moves:\n                for (int[] offset : offsets) {\n                    r2 = r + offset[0];\n                    c2 = c + offset[1];\n                    if (r2 < 0 || r2 == m || c2 < 0 || c2 == n) continue; \n\n                    if (grid[r2][c2] == \'#\') continue;\n\n                    bIdx2 = (r2*n) + c2;\n\n                    int ec = encodeCompositeIndex(bIdx2, offset);\n                    \n                    if (visited.contains(ec)) continue;\n                    \n                    int pushR2 = r - offset[0];\n                    int pushC2 = c - offset[1];\n\n                    if (pushR2 < 0 || pushR2 == m || pushC2 < 0 || pushC2 == n) continue; \n\n                    // Example 3 shows that a person can step on T\n                    if (grid[pushR2][pushC2] == \'#\') continue;\n\n                    sIdx2 = (pushR2 * n) + pushC2;\n\n                    // O(N) at worst\n                    boolean isReachable = isReachable(grid, sIdx1, sIdx2, bIdx1);\n\n                    if (!isReachable) continue;\n\n                    visited.add(ec); \n\n                    q.offer(bIdx2);\n                    qS.offer(sIdx2);\n                }\n\n            } // end single layer\n        } // end q while\n\n        return -1;\n    }\n\n    protected boolean isReachable(char[][] grid, int srcIdx, int destIdx,\n    final int boxIdx) {\n\n        int m = grid.length;\n        int n = grid[0].length;\n\n        int[] visited = new int[m*n];\n        visited[srcIdx] = 1;\n\n        int r2, c2, idx2;\n        char cell2;\n        int r1, c1, idx1;\n\n        Queue<Integer> q = new ArrayDeque<>();\n        q.offer(srcIdx);\n\n        int len = -1;\n        while (!q.isEmpty()) {\n            ++len;\n            \n            int qSz = q.size();\n\n            while (qSz > 0) {\n                --qSz;\n                idx1 = q.poll();\n\n                if (idx1 == boxIdx) continue;\n\n                if (idx1 == destIdx) return true;\n\n                r1 = idx1/n;\n                c1 = idx1 % n;\n\n                // candidate moves:\n                for (int[] offset : offsets) {\n                    r2 = r1 + offset[0];\n                    c2 = c1 + offset[1];\n                    if (r2 < 0 || r2 == m || c2 < 0 || c2 == n) continue;\n                    \n                    // example 3 implies can step on . or T\n                    if (grid[r2][c2] == boxIdx \n                    || grid[r2][c2] == \'#\') continue;\n\n                    idx2 = (r2*n) + c2;\n\n                    if (visited[idx2] != 0) continue;\n                    visited[idx2] = 1;\n\n                    q.offer(idx2);\n                }\n\n            } // end single layer\n        } // end q while\n\n        return false;\n    }\n}\n```
['Java']