2
\$\begingroup\$

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.

Improve this question
\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

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();
    }
};
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ 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. \$\endgroup\$
    – spyr03
    Jun 25, 2020 at 16:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – pacmaninbw
    Jun 25, 2020 at 17:00
  • 2
    \$\begingroup\$ 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 \$\endgroup\$
    – jtbandes
    Jun 25, 2020 at 17:05
  • \$\begingroup\$ @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. \$\endgroup\$
    – spyr03
    Jun 25, 2020 at 17:06
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Reinderien
    Jun 25, 2020 at 17:10
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.