LeetCode 1263: Minimum Moves to Move a Box to Their Target Location

Question

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by a grid of size m x n, where each element is a wall, floor, or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

• Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empty cell).
• Floor is represented by character '.' that means free cell to walk.
• Wall is represented by character '#' that means obstacle (impossible to walk there).
• There is only one box 'B' and one target cell 'T' in the grid.
• The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
• The player cannot walk through the box.
• Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Example 1:

^{Image Courtesy of LeetCode.com}

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 20
• 1 <= n <= 20
• grid contains only characters '.', '#', 'S' , 'T', or 'B'.
• There is only one character 'S', 'B' and 'T' in the grid.

Code

#include <cstdint>
#include <array>
#include <vector>
#include <utility>
#include <queue>
#include <unordered_set>

class Solution {
    using size_type = std::uint_fast16_t;
    static constexpr char kPLAYER = 'S';
    static constexpr char kBOX = 'B';
    static constexpr char kTARGET = 'T';
    static constexpr char kWALL = '#';
    static constexpr char kFLOOR = '.';
    static constexpr std::array<std::array<std::int_fast8_t, 2>, 4> kDIRECTIONS = {{{ -1, 0}, {1, 0}, {0, -1}, {0, 1}}};

public:
    int minPushBox(std::vector<std::vector<char>>& grid) {
        const size_type row_len = std::size(grid);
        const size_type col_len = std::size(grid[0]);
        std::queue<std::pair<size_type, size_type>> player_box_q;
        std::unordered_set<std::string> box_player_encodes;

        size_type start = 0;
        size_type end = 0;
        size_type player = 0;

        for (size_type row = 0; row < row_len; ++row) {
            for (size_type col = 0; col < col_len; ++col) {
                const size_type curr_pos = row * col_len + col;
                if (grid[row][col] == kPLAYER) {
                    player = curr_pos;
                    grid[row][col] = kFLOOR;
                }

                if (grid[row][col] == kBOX) {
                    start = curr_pos;
                    grid[row][col] = kFLOOR;
                }

                if (grid[row][col] == kTARGET) {
                    end = curr_pos;
                    grid[row][col] = kFLOOR;
                }
            }
        }

        if (start == end) {
            return 0;
        }

        player_box_q.push({start, player});
        size_type pushes = 0;

        while (std::size(player_box_q)) {
            size_type qlen = std::size(player_box_q);

            while (qlen--) {
                const auto curr_box_player = player_box_q.front();
                player_box_q.pop();
                const size_type box = curr_box_player.first;
                const size_type player = curr_box_player.second;

                if (box == end) {
                    return pushes;
                }

                const size_type x_box = box / col_len;
                const size_type y_box = box % col_len;

                for (const auto& direction : kDIRECTIONS) {
                    const size_type next_x_box = x_box + direction[0];
                    const size_type next_y_box = y_box + direction[1];
                    const size_type next_x_player = x_box - direction[0];
                    const size_type next_y_player = y_box - direction[1];

                    if (
                        next_x_box < 0 ||
                        next_x_box >= row_len ||
                        next_y_box < 0 ||
                        next_y_box >= col_len ||
                        grid[next_x_box][next_y_box] == kWALL
                    ) {
                        continue;
                    }


                    if (
                        next_x_player < 0 ||
                        next_x_player >= row_len ||
                        next_y_player < 0 ||
                        next_y_player >= col_len ||
                        grid[next_x_player][next_y_player] == kWALL
                    ) {
                        continue;
                    }

                    std::string box_player_encode = std::to_string(box) +
                                                    "," +
                                                    std::to_string(next_x_player * col_len + next_y_player);

                    if (box_player_encodes.count(box_player_encode)) {
                        continue;
                    }

                    if (isAccessible(grid, player, next_x_player * col_len + next_y_player, box)) {
                        player_box_q.push({next_x_box * col_len + next_y_box, box});
                        box_player_encodes.insert(box_player_encode);
                    }
                }
            }

            ++pushes;
        }

        return -1;
    }

private:
    static bool isAccessible(
        std::vector<std::vector<char>>& grid,
        const size_type start,
        const size_type end,
        const size_type box
    ) {
        const size_type row_len = std::size(grid);
        const size_type col_len = std::size(grid[0]);
        std::queue<size_type> start_q;
        std::vector<bool> valids(row_len * col_len);
        start_q.push(start);
        valids[start] = true;
        grid[box / col_len][box % col_len] = kWALL;

        while (std::size(start_q)) {
            size_type qlen = std::size(start_q);

            while (qlen--) {
                const size_type curr = start_q.front();
                start_q.pop();

                if (curr == end) {
                    grid[box / col_len][box % col_len] = kFLOOR;
                    return true;
                }

                const size_type x_start = curr / col_len;
                const size_type y_start = curr % col_len;

                for (const auto& direction : kDIRECTIONS) {
                    const size_type x_next = x_start + direction[0];
                    const size_type y_next = y_start + direction[1];
                    const size_type curr_pos = x_next * col_len + y_next;

                    if (
                        x_next < 0 ||
                        x_next >= row_len ||
                        y_next < 0 ||
                        y_next >= col_len ||
                        grid[x_next][y_next] != kFLOOR ||
                        valids[curr_pos]) {
                        continue;
                    }

                    valids[curr_pos] = true;
                    start_q.push(curr_pos);
                }
            }
        }

        grid[box / col_len][box % col_len] = kFLOOR;
        return false;
    }
};

References

• Problem

• Discuss

• Solution

Answer 1

Avoid unnecessary type conversions

kDIRECTIONS is a 2D array of std::int_fast8_t. However, these values will be added to other variables of type std::int_fast16_t. If these two types have a different size, then the compiler might have to add instructions to convert between the two, and despite having "fast" in the name, this will be slow.

Avoid overusing std::array

std::array has its uses, but here you can just use a simply C-style array:

static constexpr size_type kDIRECTIONS[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};

That is much easier to read than nested std::arrays, and will work just as well in the rest of your code without needing any modifications.

Avoid overusing std::size()

Instead of writing std::size(grid), you can write grid.size(). It avoids having to type the std::, and reads a bit more natural. Also, don't use std::size() or .size() to check if a container has members, instead use !something.empty(), like:

while (!player_box_q.empty()) {
    ...
}

The reason is that counting the number of elements can be expensive for containers that do not keep an explicit count in memory, but have to traverse the whole container to derive that number.

Use structured bindings where appropriate

Since you are writing C++17 code, you can use structured bindings, which makes code using std::pair much nicer. For example:

while (qlen--) {
    const auto [box_pos, player_pos] = player_box_q.front();
    ...

Avoid encoding things to string

I can see your reasoning: “an unordered_set<> is faster than a set<>. But the standard library doesn't know how to hash a std::pair, so I can't use an unordered_set<std::pair<size_type, size_type>. But it does allow std::string... I know, let's encode the pair to a string!” However, encoding two ints to a string is in itself quite expensive.

The proper solution is to create a custom hash function for the box/player coordinate pairs, and tell std::unordered_set to use it. There are several ways to do this, the way I will show here is to create a functor class and pass it as a template argument:

struct player_box_hash {
    std::size_t operator()(const std::pair<size_type, size_type> &key) const {
        return std::hash<uint32_t>{}(uint32_t(key.first) << 16 | key.second);
    }
};

std::unordered_set<std::pair<size_type, size_type>, player_box_hash> box_player_visited;

And now you can use it as follows:

auto box_player_encode = std::make_pair(box, next_x_player * col_len + next_y_player);

if (box_player_visited.count(box_player_encode)) {
    continue;
}

if (isAccessible(grid, player, next_x_player * col_len + next_y_player, box)) {
    player_box_q.push({next_x_box * col_len + next_y_box, box});
    box_player_visited.insert(box_player_encode);
}

Create a function to check whether a position is valid

You have duplicated the code to check whether the box's position and player's position is valid. Create a member function for it:

static bool isValidPosition(size_type x, size_type y) {
    return x >= 0 && x < row_len && ...;
}

And then use it like so:

for (const auto &direction: kDIRECTIONS) {
    ...
    if (!isValidPosition(next_x_box, next_y_box) || !isValidPosition(next_x_player, next_y_player)) {
        continue;
    }
    ...
}