Skip to content

Commit 1fcfaf0

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1391
No.1391.Check if There is a Valid Path in a Grid
1 parent 134e864 commit 1fcfaf0

File tree

4 files changed

+419
-1
lines changed

4 files changed

+419
-1
lines changed

‎solution/1300-1399/1391.Check if There is a Valid Path in a Grid/README.md

Lines changed: 143 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,7 +79,7 @@
7979

8080
<!-- 这里可写通用的实现逻辑 -->
8181

82-
并查集。
82+
并查集。判断每个单元格相邻节点是否连通，是则将其合并。最后判断 `grid[0][0]` 与 `grid[m - 1][n - 1]` 是否连通。
8383

8484
并查集模板：
8585

@@ -276,6 +276,148 @@ class Solution {
276276
}
277277
```
278278

279+
### **C++**
280+
281+
```cpp
282+
class Solution {
283+
public:
284+
vector<int> p;
285+
286+
bool hasValidPath(vector<vector<int>>& grid) {
287+
int m = grid.size();
288+
int n = grid[0].size();
289+
p.resize(m * n);
290+
for (int i = 0; i < p.size(); ++i) p[i] = i;
291+
auto left = [&] (int i, int j) {
292+
if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
293+
p[find(i * n + j)] = find(i * n + j - 1);
294+
}
295+
};
296+
auto right = [&] (int i, int j) {
297+
if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
298+
p[find(i * n + j)] = find(i * n + j + 1);
299+
}
300+
};
301+
auto up = [&] (int i, int j) {
302+
if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
303+
p[find(i * n + j)] = find((i - 1) * n + j);
304+
}
305+
};
306+
auto down = [&] (int i, int j) {
307+
if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
308+
p[find(i * n + j)] = find((i + 1) * n + j);
309+
}
310+
};
311+
for (int i = 0; i < m; ++i)
312+
{
313+
for (int j = 0; j < n; ++j)
314+
{
315+
int e = grid[i][j];
316+
if (e == 1)
317+
{
318+
left(i, j);
319+
right(i, j);
320+
}
321+
else if (e == 2)
322+
{
323+
up(i, j);
324+
down(i, j);
325+
}
326+
else if (e == 3)
327+
{
328+
left(i, j);
329+
down(i, j);
330+
}
331+
else if (e == 4)
332+
{
333+
right(i, j);
334+
down(i, j);
335+
}
336+
else if (e == 5)
337+
{
338+
left(i, j);
339+
up(i, j);
340+
}
341+
else
342+
{
343+
right(i, j);
344+
up(i, j);
345+
}
346+
}
347+
}
348+
return find(0) == find(m * n - 1);
349+
}
350+
351+
int find(int x) {
352+
if (p[x] != x) p[x] = find(p[x]);
353+
return p[x];
354+
}
355+
};
356+
```
357+
358+
### **Go**
359+
360+
```go
361+
func hasValidPath(grid [][]int) bool {
362+
m, n := len(grid), len(grid[0])
363+
p := make([]int, m*n)
364+
for i := range p {
365+
p[i] = i
366+
}
367+
var find func(x int) int
368+
find = func(x int) int {
369+
if p[x] != x {
370+
p[x] = find(p[x])
371+
}
372+
return p[x]
373+
}
374+
left := func(i, j int) {
375+
if j > 0 && (grid[i][j-1] == 1 || grid[i][j-1] == 4 || grid[i][j-1] == 6) {
376+
p[find(i*n+j)] = find(i*n + j - 1)
377+
}
378+
}
379+
right := func(i, j int) {
380+
if j < n-1 && (grid[i][j+1] == 1 || grid[i][j+1] == 3 || grid[i][j+1] == 5) {
381+
p[find(i*n+j)] = find(i*n + j + 1)
382+
}
383+
}
384+
up := func(i, j int) {
385+
if i > 0 && (grid[i-1][j] == 2 || grid[i-1][j] == 3 || grid[i-1][j] == 4) {
386+
p[find(i*n+j)] = find((i-1)*n + j)
387+
}
388+
}
389+
down := func(i, j int) {
390+
if i < m-1 && (grid[i+1][j] == 2 || grid[i+1][j] == 5 || grid[i+1][j] == 6) {
391+
p[find(i*n+j)] = find((i+1)*n + j)
392+
}
393+
}
394+
for i, row := range grid {
395+
for j, e := range row {
396+
if e == 1 {
397+
left(i, j)
398+
right(i, j)
399+
} else if e == 2 {
400+
up(i, j)
401+
down(i, j)
402+
} else if e == 3 {
403+
left(i, j)
404+
down(i, j)
405+
} else if e == 4 {
406+
right(i, j)
407+
down(i, j)
408+
} else if e == 5 {
409+
left(i, j)
410+
up(i, j)
411+
} else {
412+
right(i, j)
413+
up(i, j)
414+
}
415+
}
416+
}
417+
return find(0) == find(m*n-1)
418+
}
419+
```
420+
279421
### **...**
280422

281423
```

‎solution/1300-1399/1391.Check if There is a Valid Path in a Grid/README_EN.md

Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,8 @@ Given a <em>m</em> x <em>n</em> <code>grid</code>. Each cell of the <code>grid</
7474

7575
## Solutions
7676

77+
Union find.
78+
7779
<!-- tabs:start -->
7880

7981
### **Python3**
@@ -206,6 +208,148 @@ class Solution {
206208
}
207209
```
208210

211+
### **C++**
212+
213+
```cpp
214+
class Solution {
215+
public:
216+
vector<int> p;
217+
218+
bool hasValidPath(vector<vector<int>>& grid) {
219+
int m = grid.size();
220+
int n = grid[0].size();
221+
p.resize(m * n);
222+
for (int i = 0; i < p.size(); ++i) p[i] = i;
223+
auto left = [&] (int i, int j) {
224+
if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
225+
p[find(i * n + j)] = find(i * n + j - 1);
226+
}
227+
};
228+
auto right = [&] (int i, int j) {
229+
if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
230+
p[find(i * n + j)] = find(i * n + j + 1);
231+
}
232+
};
233+
auto up = [&] (int i, int j) {
234+
if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
235+
p[find(i * n + j)] = find((i - 1) * n + j);
236+
}
237+
};
238+
auto down = [&] (int i, int j) {
239+
if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
240+
p[find(i * n + j)] = find((i + 1) * n + j);
241+
}
242+
};
243+
for (int i = 0; i < m; ++i)
244+
{
245+
for (int j = 0; j < n; ++j)
246+
{
247+
int e = grid[i][j];
248+
if (e == 1)
249+
{
250+
left(i, j);
251+
right(i, j);
252+
}
253+
else if (e == 2)
254+
{
255+
up(i, j);
256+
down(i, j);
257+
}
258+
else if (e == 3)
259+
{
260+
left(i, j);
261+
down(i, j);
262+
}
263+
else if (e == 4)
264+
{
265+
right(i, j);
266+
down(i, j);
267+
}
268+
else if (e == 5)
269+
{
270+
left(i, j);
271+
up(i, j);
272+
}
273+
else
274+
{
275+
right(i, j);
276+
up(i, j);
277+
}
278+
}
279+
}
280+
return find(0) == find(m * n - 1);
281+
}
282+
283+
int find(int x) {
284+
if (p[x] != x) p[x] = find(p[x]);
285+
return p[x];
286+
}
287+
};
288+
```
289+
290+
### **Go**
291+
292+
```go
293+
func hasValidPath(grid [][]int) bool {
294+
m, n := len(grid), len(grid[0])
295+
p := make([]int, m*n)
296+
for i := range p {
297+
p[i] = i
298+
}
299+
var find func(x int) int
300+
find = func(x int) int {
301+
if p[x] != x {
302+
p[x] = find(p[x])
303+
}
304+
return p[x]
305+
}
306+
left := func(i, j int) {
307+
if j > 0 && (grid[i][j-1] == 1 || grid[i][j-1] == 4 || grid[i][j-1] == 6) {
308+
p[find(i*n+j)] = find(i*n + j - 1)
309+
}
310+
}
311+
right := func(i, j int) {
312+
if j < n-1 && (grid[i][j+1] == 1 || grid[i][j+1] == 3 || grid[i][j+1] == 5) {
313+
p[find(i*n+j)] = find(i*n + j + 1)
314+
}
315+
}
316+
up := func(i, j int) {
317+
if i > 0 && (grid[i-1][j] == 2 || grid[i-1][j] == 3 || grid[i-1][j] == 4) {
318+
p[find(i*n+j)] = find((i-1)*n + j)
319+
}
320+
}
321+
down := func(i, j int) {
322+
if i < m-1 && (grid[i+1][j] == 2 || grid[i+1][j] == 5 || grid[i+1][j] == 6) {
323+
p[find(i*n+j)] = find((i+1)*n + j)
324+
}
325+
}
326+
for i, row := range grid {
327+
for j, e := range row {
328+
if e == 1 {
329+
left(i, j)
330+
right(i, j)
331+
} else if e == 2 {
332+
up(i, j)
333+
down(i, j)
334+
} else if e == 3 {
335+
left(i, j)
336+
down(i, j)
337+
} else if e == 4 {
338+
right(i, j)
339+
down(i, j)
340+
} else if e == 5 {
341+
left(i, j)
342+
up(i, j)
343+
} else {
344+
right(i, j)
345+
up(i, j)
346+
}
347+
}
348+
}
349+
return find(0) == find(m*n-1)
350+
}
351+
```
352+
209353
### **...**
210354

211355
```

‎solution/1300-1399/1391.Check if There is a Valid Path in a Grid/Solution.cpp

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
class Solution {
2+
public:
3+
vector<int> p;
4+
5+
bool hasValidPath(vector<vector<int>>& grid) {
6+
int m = grid.size();
7+
int n = grid[0].size();
8+
p.resize(m * n);
9+
for (int i = 0; i < p.size(); ++i) p[i] = i;
10+
auto left = [&] (int i, int j) {
11+
if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
12+
p[find(i * n + j)] = find(i * n + j - 1);
13+
}
14+
};
15+
auto right = [&] (int i, int j) {
16+
if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
17+
p[find(i * n + j)] = find(i * n + j + 1);
18+
}
19+
};
20+
auto up = [&] (int i, int j) {
21+
if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
22+
p[find(i * n + j)] = find((i - 1) * n + j);
23+
}
24+
};
25+
auto down = [&] (int i, int j) {
26+
if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
27+
p[find(i * n + j)] = find((i + 1) * n + j);
28+
}
29+
};
30+
for (int i = 0; i < m; ++i)
31+
{
32+
for (int j = 0; j < n; ++j)
33+
{
34+
int e = grid[i][j];
35+
if (e == 1)
36+
{
37+
left(i, j);
38+
right(i, j);
39+
}
40+
else if (e == 2)
41+
{
42+
up(i, j);
43+
down(i, j);
44+
}
45+
else if (e == 3)
46+
{
47+
left(i, j);
48+
down(i, j);
49+
}
50+
else if (e == 4)
51+
{
52+
right(i, j);
53+
down(i, j);
54+
}
55+
else if (e == 5)
56+
{
57+
left(i, j);
58+
up(i, j);
59+
}
60+
else
61+
{
62+
right(i, j);
63+
up(i, j);
64+
}
65+
}
66+
}
67+
return find(0) == find(m * n - 1);
68+
}
69+
70+
int find(int x) {
71+
if (p[x] != x) p[x] = find(p[x]);
72+
return p[x];
73+
}
74+
};

0 commit comments

Comments
 (0)