-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
63 lines (52 loc) · 1.36 KB
/
Solution.cs
File metadata and controls
63 lines (52 loc) · 1.36 KB
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
public class Solution
{
public int SlidingPuzzle(int[][] board)
{
var target = "123450";
var start = "";
for (var i = 0; i < 2; i++)
{
for (var j = 0; j < 3; j++)
{
start += board[i][j].ToString();
}
}
if (start == target) return 0;
int[][] moves = [
[1, 3],
[0, 2, 4],
[1, 5],
[0, 4],
[1, 3, 5],
[2, 4]
];
var queue = new Queue<(string, int)>();
var visited = new HashSet<string>();
queue.Enqueue((start, 0));
visited.Add(start);
while (queue.Count > 0)
{
var (current, steps) = queue.Dequeue();
var zeroIndex = current.IndexOf('0');
if (current == target)
{
return steps;
}
foreach (var move in moves[zeroIndex])
{
var newConfig = Swap(current, zeroIndex, move);
if (visited.Add(newConfig))
{
queue.Enqueue((newConfig, steps + 1));
}
}
}
return -1;
}
private string Swap(string s, int i, int j)
{
var arr = s.ToCharArray();
(arr[i], arr[j]) = (arr[j], arr[i]);
return new string(arr);
}
}