1631. Path With Minimum Effort

• 시작점 (0,0) 부터 끝점 (N - 1, M - 1)까지 BFS로 탐색하면서 각 경로의 최소 effort을 memoize하는 방식으로 해결했다.

class Solution {
public:
    static inline void checkNext(
        vector<vector<int>>& heights,
        vector<vector<int>>& efforts,
        queue<pair<int, int>>& q,
        int i, int j, int di, int dj, int R, int C
    ) {
        int *curr, *next, diff;
        int ni = i + di, nj = j + dj;
        if (ni < 0 || ni >= R || nj < 0 || nj >= C) return;
        curr = &efforts[i][j];
        next = &efforts[ni][nj];
        diff = max(*curr, abs(heights[i][j] - heights[ni][nj]));
        if (*next == -1 || diff < *next) {
            *next = diff;
            q.emplace(ni, nj);
        }
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        // initialize efforts
        vector<vector<int>> efforts;
        int R = heights.size();
        int C = heights[0].size();
        efforts.reserve(R);
        for (int i = 0; i < R; ++i) {
            vector<int> elems(C);
            std::fill(elems.begin(), elems.end(), -1);
            efforts.emplace_back(std::move(elems));
        }
        efforts[0][0] = 0;
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        int i, j;
        while (!q.empty()) {
            tie(i, j) = q.front();
            q.pop();
            checkNext(heights, efforts, q, i, j, -1,  0, R, C);
            checkNext(heights, efforts, q, i, j,  1,  0, R, C);
            checkNext(heights, efforts, q, i, j,  0, -1, R, C);
            checkNext(heights, efforts, q, i, j,  0,  1, R, C);
        }
        return efforts[R - 1][C - 1];
    }
};