LeetCode 1293: Shortest Path in a Grid with Obstacles Elimination

Question

I'm posting my code for a LeetCode problem copied here. If you have time and would like to review, please do so.

Problem

• Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

• Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

Constraints:

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] == 0 or 1
• grid[0][0] == grid[m-1][n-1] == 0

Accepted Code

#include <array>
#include <string>
#include <vector>
#include <unordered_set>
#include <utility>
#include <algorithm>
class Solution {
public:
 inline int shortestPath(const std::vector<std::vector<int>>& grid, const int k) {
 if (grid.empty()) {
 return 0;
 }
 int path_distance = INT_MAX;
 get_manhattan_distance(0, -1, -1, 0, 0, k, grid, path_distance);
 return path_distance == INT_MAX ? -1 : path_distance;
 }
private:
 // Four neighbor cells
 static inline std::array<std::pair<int, int>, 4> directions = {{{0, 1}, {1, 0}, {0, -1}, { -1, 0}}};
 std::unordered_set<std::string> memo;
 // row - col - k string
 static inline std::string get_key(const int row, const int col, const int k) {
 return std::to_string(row) + "#" + std::to_string(col) + "#" + std::to_string(k);
 }
 // Calculate Manhattan distance 
 inline void get_manhattan_distance(const int path, const int prev_row, const int prev_col, const int row, const int col, int k, const std::vector<std::vector<int>>& grid, int& base_distance) {
 if (k >= get_row_length(grid) + get_col_length(grid) - 3 - row - col) {
 base_distance = min(base_distance, path + get_row_length(grid) + get_col_length(grid) - 2 - row - col);
 return;
 }
 if (row == get_row_length(grid) - 1 && col == get_col_length(grid) - 1) {
 base_distance = min(base_distance, path);
 return;
 }
 if (!memo.insert(get_key(row, col, k)).second) {
 return;
 }
 int curr_dist = get_distance(row, col, grid);
 for (const auto& direction : directions) {
 if (!(row + direction.first == prev_row && col + direction.second == prev_col) && is_valid(row + direction.first, col + direction.second, grid)) {
 int dist = get_distance(row + direction.first, col + direction.second, grid);
 if (grid[row + direction.first][col + direction.second] == 0) {
 get_manhattan_distance(path + 1, row, col, row + direction.first, col + direction.second, k, grid, base_distance);
 } else if (dist < curr_dist && k > 0) {
 get_manhattan_distance(path + 1, row, col, row + direction.first, col + direction.second, k - 1, grid, base_distance);
 }
 }
 }
 }
 // Get Current distance
 static inline const int get_distance(const int row, const int col, const std::vector<std::vector<int>>& grid) {
 return std::abs(row - get_row_length(grid) - 1) + std::abs(col - get_col_length(grid) - 1);
 }
 // Check for grid boundaries
 static inline const bool is_valid(const int row, const int col, const std::vector<std::vector<int>>& grid) {
 return row > -1 && row < get_row_length(grid) && col > -1 && col < get_col_length(grid);
 }
 // Get grid row size
 static inline const int get_row_length(const std::vector<std::vector<int>>& grid) {
 return grid.size();
 }
 // Get grid column size
 static inline const int get_col_length(const std::vector<std::vector<int>>& grid) {
 return grid[0].size();
 }
};

Reference

LeetCode has a template for answering question. There is usually a class named Solution with one or more public functions which we are not allowed to rename.

• Problem

• Discuss

• Taxicab Geometry

Answer 1

The C++ key word inline is pretty much obsolete.^{1 2} Since at least C++03 inline is a recommendation to the compiler and nothing more. In the LeetCode environment it may help, but most C++ compilers are optimizing compilers and when code is compiled -O3 for maximum optimization the compiler decides what should and should not be inlined and ignores the keyword.

#include <array>
#include <string>
#include <vector>
#include <unordered_set>
#include <utility>
#include <algorithm>
class Solution {
public:
 int shortestPath(const std::vector<std::vector<int>>& grid, const int k) {
 if (grid.empty()) {
 return 0;
 }
 int path_distance = INT_MAX;
 get_manhattan_distance(0, -1, -1, 0, 0, k, grid, path_distance);
 return path_distance == INT_MAX ? -1 : path_distance;
 }
private:
 // Four neighbor cells
 constexpr static std::array<std::pair<int, int>, 4> directions = {{{0, 1}, {1, 0}, {0, -1}, { -1, 0}}};
 std::unordered_set<std::string> memo;
 // row - col - k string
 static std::string get_key(const int row, const int col, const int k) {
 return std::to_string(row) + "#" + std::to_string(col) + "#" + std::to_string(k);
 }
 // Calculate Manhattan distance
 void get_manhattan_distance(const int path, const int prev_row, const int prev_col, const int row, const int col, int k, const std::vector<std::vector<int>>& grid, int& base_distance) {
 if (k >= get_row_length(grid) + get_col_length(grid) - 3 - row - col) {
 base_distance = std::min(base_distance, path + get_row_length(grid) + get_col_length(grid) - 2 - row - col);
 return;
 }
 if (row == get_row_length(grid) - 1 && col == get_col_length(grid) - 1) {
 base_distance = std::min(base_distance, path);
 return;
 }
 if (!memo.insert(get_key(row, col, k)).second) {
 return;
 }
 int curr_dist = get_distance(row, col, grid);
 for (const auto& direction : directions) {
 if (!(row + direction.first == prev_row && col + direction.second == prev_col) && is_valid(row + direction.first, col + direction.second, grid)) {
 int dist = get_distance(row + direction.first, col + direction.second, grid);
 if (grid[row + direction.first][col + direction.second] == 0) {
 get_manhattan_distance(path + 1, row, col, row + direction.first, col + direction.second, k, grid, base_distance);
 } else if (dist < curr_dist && k > 0) {
 get_manhattan_distance(path + 1, row, col, row + direction.first, col + direction.second, k - 1, grid, base_distance);
 }
 }
 }
 }
 // Get Current distance
 static int get_distance(const int row, const int col, const std::vector<std::vector<int>>& grid) {
 return std::abs(row - get_row_length(grid) - 1) + std::abs(col - get_col_length(grid) - 1);
 }
 // Check for grid boundaries
 static const bool is_valid(const int row, const int col, const std::vector<std::vector<int>>& grid) {
 return row > -1 && row < get_row_length(grid) && col > -1 && col < get_col_length(grid);
 }
 // Get grid row size
 static int get_row_length(const std::vector<std::vector<int>>& grid) {
 return grid.size();
 }
 // Get grid column size
 static int get_col_length(const std::vector<std::vector<int>>& grid) {
 return grid[0].size();
 }
};

• spyr03: I don't think it is fair to assume that -O3 is used. A small survey of online coding environments show that more use -O2 than -O3. On Leetcode discuss there are at least two unanswered questions on what the cpp compiler options are set to. I was unable to find an answer for Leetcode (, Hackerrank, or SPOJ). Codeforces, Codechef, ACM-ICPC, and UVa state that code is compiled with -O2, not the maximum optimisation level. Topcoder now uses -O3, but that is a recent change from sometime in the last 3 years. Google Code Jam uses -O3.
• pacmaninbw: @spyr03 And my review states that it might help in the LeetCode Environment but released code should be -O3, at least in my 30+ years of experience. Note it wasn't until more than 4 years ago that here on Code Review that I learned about this.
• jtbandes: This is not completely accurate. inline is still meaningful, and required in some circumstances — it's just not related to optimization. Read more here: stackoverflow.com/a/5971755/23649
• spyr03: @pacmaninbw My point is that I disagree with your first statement "inline is pretty much obsolete" as that relies on -O3 being set, and that is not true in general, nor in the common case of online coding environments.
• Reinderien: I think the general sentiment holds true. inline, certainly when used here and very often elsewhere, is an instance of both premature optimization as well as probably-ineffectual optimization, and is safe to discard.

Answer 2

Appending to a string

For this:

std::to_string(row) + "#" + std::to_string(col) + "#" + std::to_string(k);

Check the list of overloads. One of them accepts a character, which you should prefer to using a string.

Const results

This:

inline const int get_distance(...

does not benefit from declaring the return value const. Integers are immutable anyway.