773. Sliding Puzzle
Approach
BFS on board states encoded as strings; find the blank '0', swap it with each valid neighbor, and expand until target reached.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: BFS on board states encoded as strings; find the blank '0', swap it with each valid neighbor, and expand until target reached.
// Time: O((m·n)!) Space: O((m·n)!)
public class Solution
{
public int SlidingPuzzle(int[][] board)
{
int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
int m = 2;
int n = 3;
string goal = "123450";
StringBuilder startSb = new StringBuilder();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
startSb.Append((char)('0' + board[i][j]));
string start = startSb.ToString();
if (start.Equals(goal))
return 0;
Queue<string> q = new Queue<string>(new List<string> { start });
HashSet<string> seen = new HashSet<string>(new List<string> { start });
for (int step = 1; q.Count > 0; ++step)
{
for (int sz = q.Count; sz > 0; --sz)
{
string s = q.Dequeue();
int zeroIndex = s.IndexOf("0");
int i = zeroIndex / n;
int j = zeroIndex % n;
foreach (var dir in dirs)
{
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
int swappedIndex = x * n + y;
StringBuilder sb = new StringBuilder(s);
sb[zeroIndex] = s[swappedIndex];
sb[swappedIndex] = s[zeroIndex];
string t = sb.ToString();
if (t.Equals(goal))
return step;
if (!seen.Contains(t))
{
q.Enqueue(t);
seen.Add(t);
}
}
}
}
return -1;
}
}