LeetCode 솔루션

[5/16] 1091. Shortest Path in Binary Matrix

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.16 12:51

7,561 조회
2 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 5월 16일 문제입니다.

https://leetcode.com/problems/shortest-path-in-binary-matrix/

1091. Shortest Path in Binary Matrix

Medium

3279149Add to ListShare

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

#LeetCode, #Facebook, #Amazon, #Microsoft, #Google, #Snapchat, #Adobe, #Uber, #Bloomberg, #Citadel, #Oracle, #Twitter, #Paypal, #JPMorgan, #Array, #Breadth-First Search(BFS), #Matrix

링크

https://leetcode.com/problems/shortest-path-in-binary-matrix/ 2473 회 연결

익명
작성일 2022.05.16 14:04

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        stack<pair<int, int>> s, n;        
        s.emplace(0, 0);
        for(int ret = 1, height = grid.size(), width = grid[0].size(); !s.empty(); swap(s, n), ++ret) {
            while(!s.empty()) {
                auto [y, x] = s.top();s.pop();
                if (y < 0 || x < 0 || y == height || x == width || grid[y][x]) continue;
                if (y == height - 1 && x == width - 1) return ret;
                grid[y][x] = 1;
                for(auto [dy, dx] : vector<pair<int, int>>{
                    {0, -1}, {1, -1}, {-1, -1}, {1, 0}, {-1, 0}, {0, 1}, {-1, 1}, {1, 1}}) n.emplace(y+dy, x+dx);
            }
        }
        return -1;
    }
};

익명
작성일 2022.05.16 17:14

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        que = []
        dir = [[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1]]
        if grid[0][0] == 1: return -1
        if len(grid) == 1: return 1
        que.append((0,0,1))
        visited = set()
        visited.add((0,0))
        nr = len(grid)
        nc = len(grid[0])
        ans = float(inf)
        while que:
            front = que.pop(0)
            cy = front[0]
            cx = front[1]
            ccnt = front[2]
            for y, x in dir:
                ny = cy + y
                nx = cx + x
                if ny < 0 or nx < 0 or ny >= nr or nx >= nc: continue
                if grid[ny][nx] == 1: continue
                if (ny, nx) in visited: continue
                if ny == nr-1 and nx == nc-1:
                    ans = min(ans, ccnt + 1)
                visited.add((ny, nx))
                que.append((ny, nx, ccnt + 1))
        print(visited)
        if ans == float(inf):
            return -1
        else:
            return ans

[code=python]class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        que = []
        dir = [[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1]]
        if grid[0][0] == 1: return -1
        if len(grid) == 1: return 1
        que.append((0,0,1))
        visited = set()
        visited.add((0,0))
        nr = len(grid)
        nc = len(grid[0])
        ans = float(inf)
        while que:
            front = que.pop(0)
            cy = front[0]
            cx = front[1]
            ccnt = front[2]
            for y, x in dir:
                ny = cy + y
                nx = cx + x
                if ny < 0 or nx < 0 or ny >= nr or nx >= nc: continue
                if grid[ny][nx] == 1: continue
                if (ny, nx) in visited: continue
                if ny == nr-1 and nx == nc-1:
                    ans = min(ans, ccnt + 1)
                visited.add((ny, nx))
                que.append((ny, nx, ccnt + 1))
        print(visited)
        if ans == float(inf):
            return -1
        else:
            return ans
        [/code]