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

Question

I'm posting a follow-up code on this question, which seems to be a version of Sokoban.

enter image description here

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:

enter image description here

^{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::int_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 size_type kDIRECTIONS[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
 int minPushBox(std::vector<std::vector<char>>& grid) {
 const size_type row_len = grid.size();
 const size_type col_len = grid[0].size();
 std::queue<std::pair<size_type, size_type>> player_box_q;
 std::unordered_set<std::pair<size_type, size_type>, player_box_hash> box_player_visited;
 size_type start = 0;
 size_type end = 0;
 size_type player_pos = 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;
 setCurrentPosition(grid, row, col, curr_pos, start, end, player_pos);
 }
 }
 if (start == end) {
 return 0;
 }
 player_box_q.push({start, player_pos});
 size_type pushes = 0;
 while (player_box_q.size()) {
 size_type qlen = player_box_q.size();
 while (qlen--) {
 const auto [box_pos, player_pos] = player_box_q.front();
 player_box_q.pop();
 if (box_pos == end) {
 return pushes;
 }
 const size_type x_box = box_pos / col_len;
 const size_type y_box = box_pos % 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 (!isValidPosition(next_x_box, next_y_box, row_len, col_len, grid) || !isValidPosition(next_x_player, next_y_player, row_len, col_len, grid)) {
 continue;
 }
 auto box_player_encode = std::make_pair(box_pos, next_x_player * col_len + next_y_player);
 if (box_player_visited.count(box_player_encode)) {
 continue;
 }
 if (isAccessible(grid, player_pos, next_x_player * col_len + next_y_player, box_pos)) {
 player_box_q.push({next_x_box * col_len + next_y_box, box_pos});
 box_player_visited.insert(box_player_encode);
 }
 }
 }
 ++pushes;
 }
 return -1;
 }
private:
 struct player_box_hash {
 std::size_t operator()(const std::pair<size_type, size_type>& key) const {
 return std::hash<size_type> {}(size_type(key.first) << 8 | key.second);
 }
 };
 static bool isValidPosition(
 const size_type x,
 const size_type y,
 const size_type& col_len,
 const size_type& row_len,
 const std::vector<std::vector<char>>& grid
 ) {
 return x >= 0 && x < col_len && y >= 0 && y < row_len && grid[x][y] != kWALL;
 }
 static void setCurrentPosition(
 std::vector<std::vector<char>>& grid,
 const size_type& row,
 const size_type& col,
 const size_type& curr_pos,
 size_type& start,
 size_type& end,
 size_type& player_pos
 
 ) {
 if (grid[row][col] == kPLAYER) {
 player_pos = 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;
 }
 }
 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 = grid.size();
 const size_type col_len = grid[0].size();
 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 (start_q.size()) {
 size_type qlen = start_q.size();
 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

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

• Sokoban C++

• Problem

• Discuss

• Solution