# LeetCode 1293: Shortest Path in a Grid with Obstacles Elimination

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.

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();
}
};

• 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. Jun 25, 2020 at 16:58
• @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. Jun 25, 2020 at 17:00
• 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 Jun 25, 2020 at 17:05
• @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. Jun 25, 2020 at 17:06
• 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. Jun 25, 2020 at 17:10

## 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.