[C++] BFS with deque
0-1 BFS implemented by deque: when the new state pushes the box, push it to the back of the deque; otherwise push front. In this way, every node we pop from the
0-1 BFS implemented by deque: when the new state pushes the box, push it to the back of the deque; otherwise push front. In this way, every node we pop from the deque has the smallest number of pushes in the deque.\n\nPriority queue can also be used instead of deque. My results for both methods:\ndeque: 120ms 16MB\npriority queue: 760ms 8MB\n\n```\nclass Solution {\n    typedef pair<int, pair<int, int>> PIII;\npublic:\n    int minPushBox(vector<vector<char>>& grid) {\n        int M = grid.size();\n        int N = grid[0].size();\n        deque<PIII> dq;\n        int box = -1, start = -1;\n        for (int i = 0; i < M; i++) {\n            for (int j = 0; j < N; j++) {\n                if (grid[i][j] == \'B\') box = i*N+j;\n                if (grid[i][j] == \'S\') start = i*N+j;  \n            }\n        }\n        dq.push_back({0, {box, start}});\n        vector<vector<bool>> visited(M*N, vector<bool>(M*N, false));\n        int dir1[] = {0, 0, -1, 1};\n        int dir2[] = {-1, 1, 0, 0};\n        while (!dq.empty()) {\n            int push = dq.front().first;\n            int b_pos = dq.front().second.first;\n            int p_pos = dq.front().second.second;\n            dq.pop_front();\n            if (visited[b_pos][p_pos]) continue;\n            visited[b_pos][p_pos] = true;\n            int rb = b_pos/N, cb = b_pos%N;\n            int rp = p_pos/N, cp = p_pos%N;\n            for (int i = 0; i < 4; i++) {\n                int nr = rp + dir1[i];\n                int nc = cp + dir2[i];\n                if (nr < 0 || nc < 0 || nr >= M || nc >= N || grid[nr][nc] == \'#\') continue;\n                if (nr*N+nc != b_pos) {\n                    dq.push_front({push, {b_pos, nr*N+nc}});\n                }\n                else { // move box\n                    int nrb = rb + dir1[i], ncb = cb+dir2[i];\n                    if (nrb < 0 || ncb < 0 || nrb >= M || ncb >= N || grid[nrb][ncb] == \'#\') continue;\n                    if (grid[nrb][ncb] == \'T\') return push+1;\n                    dq.push_back({push+1, {nrb*N+ncb, b_pos}});\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
[]