Created
March 3, 2019 20:56
-
-
Save leeelton/180ed9ed364225cb379dee51a5a08e1e to your computer and use it in GitHub Desktop.
BFS Daily Coding Challenge 55
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on. | |
Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board. | |
For example, given the following board: | |
[[f, f, f, f], | |
[t, t, f, t], | |
[f, f, f, f], | |
[f, f, f, f]] | |
and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row. | |
*/ | |
/* | |
modified BFS, where we store the current number of steps along witht he current node | |
visited[board.size][board.size] | |
queue | |
queue.enquqeue(PositionLength(start, 0))) | |
while !queue.isEmpty | |
let cur = queue.dequeue() | |
visited[cur.position] = true | |
if cur.position = end { | |
return cur.length | |
} | |
let neighbors: [PosiitonLneght] = getNeighbors(cur, baord) | |
for neghbor in nehgbors | |
if !visited[neighbor.position] | |
queue.enqueue(neighbor) | |
return nil | |
O(V*E) = O(n^2) run time | |
O(V+E) = O(n^2) space for the visited array | |
*/ | |
struct PositionLength { | |
var position: Coordinate | |
var length: Int | |
} | |
struct Coordinate: Equatable { | |
var row: Int | |
var col: Int | |
} | |
func minSteps(board: [[Bool]], start: Coordinate, end: Coordinate) -> Int? { | |
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: board.count), count: board.count) | |
var queue: [PositionLength] = [] | |
queue.append(PositionLength(position: start, length: 0)) | |
while !queue.isEmpty { | |
let cur: PositionLength = queue.removeFirst() | |
visited[cur.position.row][cur.position.col] = true | |
if cur.position == end { | |
return cur.length | |
} | |
let neighbors: [PositionLength] = getNeighbors(position:cur, board: board) | |
for neighbor in neighbors { | |
if !visited[neighbor.position.row][neighbor.position.col] { | |
queue.append(neighbor) | |
} | |
} | |
} | |
return nil | |
} | |
func getNeighbors(position: PositionLength, board: [[Bool]]) -> [PositionLength] { | |
// valid neighbor not outof bounds | |
// valid neighbor in board has a value of false | |
// right | |
var neighbors: [PositionLength] = [] | |
let curCol = position.position.col | |
let curRow = position.position.row | |
let curLen = position.length | |
// Right | |
let right = curCol + 1 | |
if right < board.count && board[curRow][right] != true { | |
let temp = Coordinate(row:curRow, col:right) | |
neighbors.append(PositionLength(position: temp, length: curLen+1)) | |
} | |
// Bottom | |
let bottom = curRow + 1 | |
if bottom < board.count && board[bottom][curCol] != true { | |
let temp = Coordinate(row:bottom, col:curCol) | |
neighbors.append(PositionLength(position: temp, length: curLen+1)) | |
} | |
// Top | |
let top = curRow - 1 | |
if top >= 0 && board[top][curCol] != true { | |
let temp = Coordinate(row:top, col:curCol) | |
neighbors.append(PositionLength(position: temp, length: curLen+1)) | |
} | |
// Left | |
let left = curCol - 1 | |
if left >= 0 && board[curRow][left] != true { | |
let temp = Coordinate(row:curRow, col:left) | |
neighbors.append(PositionLength(position: temp, length: curLen+1)) | |
} | |
return neighbors | |
} | |
let board: [[Bool]] = [ | |
[false, false, false, false], | |
[true, true, true, false], | |
[false, false, false, false], | |
[false, false, false, false] | |
] | |
let start = Coordinate(row: 2, col: 0) | |
let end = Coordinate(row: board.count-1, col: board.count-1) | |
print("\(minSteps(board:board, start:start, end:end) ?? -1)") | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment