Dyalog APL, 27 characters
⎕ evaluated input. APL distinguishes between a matrix and a vector of vectors. This program assumes that the input is a matrix.
(~×⍳∘⍴)A is a fork equivalent to
(~A) × ⍳⍴A. It's needed to avoid mentioning
⎕ twice or introducing a variable.
⍴A is the shape of
A. For a 4-by-7 matrix the shape is
⍳ is the index generator.
1 2 3 4.
⍳4 7 is the vectors
(1 1)(1 2)...(4 7) arranged in a 4-by-7 matrix.
~A flips the bits of
× by multiplying
⍳⍴A by the flipped bits, we preserve the coordinates of all free cells and turn all walls into
, ravels the matrix of coordinate pairs, i.e. linearizes it into a vector. In this case the vector will consist of pairs.
A∘.-A subtracts elements of
A pairwise. Note that here the elements of
A are themselves pairs.
| absolute value
+/¨ sum each pair of absolute values. This gives us the grid distances between every pair of cells in the maze, save for walls.
1≥ we are only intrested in neighbours at a distance no more than 1, this also excludes walls. Now we have a graph's adjacency matrix.
∨.∧⍨⍣≡ Floyd--Warshall's transitive closure algorithm
(f⍣n)A (not used here) where
n is an integer is the power operator. It applies
f f ... f A.
g is a function, is the fixed point operator, a.k.a. "power limit". It keeps on computing the series
f f A, ... until
((f⍣i)A) g ((f⍣(i+1))A) returns true for some
i. In this case we use match (
A∨.∧A is a step in Floyd's algorithm.
f.g is a generalisation of matrix multiplication (
+.×), here we use conjunction (
∧) and disjunction (
∨) in place of
⍣≡ has applied the step enough times and reached a stable state, we must look up the top-right corner of the matrix to get the result, so we flip it (
⌽) and take the first, top-left item (