14:T543,class DisjointSet { public: vector f; DisjointSet(int n) { f.resize(n); iota(f.begin(), f.end(), 0); } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void merge(int x, int y) { f[find(x)] = find(y); } }; class Solution { public: bool hasValidPath(vector>& grid) { int m = grid.size(), n = grid[0].size(); vector patterns = {0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011}; vector> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; DisjointSet ds(m * n); for (int x = 0; x < m; ++x) { for (int y = 0; y < n; ++y) { int pattern = patterns[grid[x][y]]; for (int i = 0; i < 4; ++i) { if (pattern & (1 << i)) { int nx = x + dirs[i].first, ny = y + dirs[i].second; if (nx >= 0 && nx < m && ny >= 0 && ny < n) { int nPattern = patterns[grid[nx][ny]]; if (nPattern & (1 << ((i + 2) % 4))) { ds.merge(x * n + y, nx * n + ny); } } } } } } return ds.find(0) == ds.find(m * n - 1); } };15:T4c5,class DisjointSet { constructor(n) { this.f = Array.from({length: n}, (_, i) => i); } find(x) { if (x === this.f[x]) return x; return this.f[x] = this.find(this.f[x]); } merge(x, y) { this.f[this.find(x)] = this.find(y); } } var hasValidPath = function(grid) { const m = grid.length, n = grid[0].length; const patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]; const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]; const ds = new DisjointSet(m * n); for (let x = 0; x < m; x++) { for (let y = 0; y < n; y++) { const pattern = patterns[grid[x][y]]; for (let i = 0; i < 4; i++) { if ((pattern & (1 << i)) !== 0) { const nx = x + dirs[i][0], ny = y + dirs[i][1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n) { const nPattern = patterns[grid[nx][ny]]; if ((nPattern & (1 << ((i + 2) % 4))) !== 0) { ds.merge(x * n + y, nx * n + ny); } } } } } } return ds.find(0) === ds.find(m * n - 1); };

Time Complexity

Space Complexity