Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1391. Check if There is a Valid Path in a Grid

---

題目：


解答：

class Solution {
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pair<int, int>> mov = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
        };
        vector<vector<int>> dir = {
            {},
            {1, 3},
            {0, 2},
            {2, 3},
            {1, 2},
            {0, 3},
            {0, 1}
        };
        vector<int> opposite = {2, 3, 0, 1};

        queue<pair<int, int>> q;

        q.push({0, 0});
        visited[0][0] = true;

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            if (r == m - 1 && c == n - 1) {
                return true;
            }

            int t = grid[r][c];
            for (int d : dir[t]) {
                int nr = r + mov[d].first;
                int nc = c + mov[d].second;

                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }

                if (visited[nr][nc]) {
                    continue;
                }
                
                int nt = grid[nr][nc];
                for (int nd : dir[nt]) {
                    if (nd == opposite[d]) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                        break;
                    }
                }
            }
        }

        return false;
    }
};