Monday, March 26, 2018

find path out of a maze

For left, right, up, down directions.
path maze(m, r = 0, c = 0):
    if m == null || m.length() == 0 || m[0].length() == 0:
        throw
    rows = m.length()
    cols = m[0].length()
    path = new
    mazeInner(m, r, c, rows, cols, path)
    return path

bool mazeInner(m, r = 0, c = 0, rows, cols,
    path, blocked = new bool[rows][cols]):
    if !(0 <= r < rows) || !(0 <= c < cols):
        return false
    if hasObstacle(m, r, c):
        return false
    if blocked[r][c]:
        return false
    if path.has(r, c):
        return false
    path.add((r, c))
    if isExit(m, r, c):
        return true
    if (m, r+1, c, rows, cols, path, visited):
        return true
    if (m, r-1, c, rows, cols, path, visited):
        return true
    if (m, r, c+1, rows, cols, path, visited):
        return true
    if (m, r, c-1, rows, cols, path, visited):
        return true
    path.removeLast()
    blocked[r][c] = true
    return false

bool isObstacle(m, r, c):
    return m[r][c] == -1
bool isExit(m, r, c):
    return m[r][c] == 1

No comments:

Post a Comment