-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
64 lines (63 loc) · 2.44 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using System;
using System.Collections.Generic;
using System.Linq;
namespace CheckIfThereIsAValidPathInAGrid
{
class Program
{
static void Main(string[] args)
{
int[][] grid =
{
new[] {1, 1, 2},
};
Console.WriteLine(HasValidPath_BFS(grid));
}
static bool HasValidPath_BFS(int[][] grid)
{
if (grid.Length == 0 || grid[0].Length == 0) return false;
if (grid.Length == 1 && grid[0].Length == 1) return true;
int[][][] directions =
{
new[] {new[] {0, -1, 11, 14, 16}, new[] {0, 1, 11, 13, 15}},
new[] {new[] {-1, 0, 12, 13, 14}, new[] {1, 0, 12, 15, 16}},
new[] {new[] {0, -1, 11, 14, 16}, new[] {1, 0, 12, 15, 16}},
new[] {new[] {0, 1, 11, 13, 15}, new[] {1, 0, 12, 15, 16}},
new[] {new[] {0, -1, 11, 14, 16}, new[] {-1, 0, 12, 13, 14}},
new[] {new[] {-1, 0, 12, 13, 14}, new[] {0, 1, 11, 13, 15}}
};
int[][] mark = new int[grid.Length][];
for (int i = 0; i < mark.Length; i++)
mark[i] = new int[grid[0].Length];
var queue = new Queue<int[]>();
queue.Enqueue(new []{0, 0});
mark[0][0]++;
while (queue.Count != 0)
{
var cur = queue.Dequeue();
var street = grid[cur[0]][cur[1]];
for (int i = 0; i < 2; i++)
{
var newX = cur[0] + directions[street - 1][i][0];
var newY = cur[1] + directions[street - 1][i][1];
if (newX < 0 || newX >= grid.Length || newY < 0 || newY >= grid[0].Length) continue;
if (!directions[street - 1][i].Contains(grid[newX][newY] + 10))
return false;
if (newX == grid.Length - 1 && newY == grid[0].Length - 1) return true;
if (mark[newX][newY] == 0)
{
mark[newX][newY]++;
queue.Enqueue(new []{newX, newY});
}
else
{
mark[newX][newY]++;
if(mark[newX][newY] == 3 && newX != 0 && newY != 0)
return false;
}
}
}
return false;
}
}
}