1+ /**
2+ * Question Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/
3+ */
4+
5+ class ListNode {
6+ let val : [ Int ]
7+ var next : ListNode ?
8+
9+ init ( _ val: [ Int ] ) {
10+ self . val= val
11+ }
12+ }
13+
14+ class Dequeue {
15+ var head : ListNode ?
16+ var tail : ListNode ?
17+ var size = 0
18+
19+ func enqueue( _ val: [ Int ] ) {
20+ let node = ListNode ( val)
21+ if head== nil {
22+ head= node
23+ tail= node
24+ } else {
25+ tail? . next= node
26+ tail= tail? . next
27+ }
28+
29+ size+= 1
30+ }
31+
32+ func deque( ) -> [ Int ] ? {
33+ if head== nil {
34+ return nil
35+ }
36+
37+ let node = head
38+ head= head? . next
39+ if head== nil {
40+ tail= nil
41+ }
42+
43+ size-= 1
44+ return node!. val
45+ }
46+ }
47+
48+ class Solution {
49+ func shortestPathBinaryMatrix( _ grid: [ [ Int ] ] ) -> Int {
50+ let rows = grid. count
51+ let cols = grid [ 0 ] . count
52+ var visit = Set < [ Int ] > ( )
53+ var deque = Dequeue ( )
54+ visit. insert ( [ 0 , 0 ] )
55+ deque. enqueue ( [ 0 , 0 , 1 ] )
56+
57+ while deque. size> 0 {
58+ let val = deque. deque ( ) !
59+ let r = val [ 0 ]
60+ let c = val [ 1 ]
61+ let len = val [ 2 ]
62+
63+ if r< 0 || c< 0 || r== rows || c== cols ||grid [ r] [ c] == 1 {
64+ continue
65+ }
66+
67+ if r== rows- 1 && c== cols- 1 {
68+ return len
69+ }
70+
71+ let directions = [ ( 0 , 1 ) , ( 0 , - 1 ) , ( 1 , 0 ) , ( - 1 , 0 ) , ( - 1 , - 1 ) , ( 1 , 1 ) , ( - 1 , 1 ) , ( 1 , - 1 ) ]
72+ for (dr, dc) in directions{
73+ if !visit. contains ( [ r+ dr, c+ dc] ) {
74+ deque. enqueue ( [ r+ dr, c+ dc, len+ 1 ] )
75+ visit. insert ( [ r+ dr, c+ dc] )
76+ }
77+ }
78+ }
79+
80+ return - 1
81+ }
82+ }