엔지니어 게시판
LeetCode 솔루션 분류

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

컨텐츠 정보

본문

[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.

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

관련자료

댓글 2

austin님의 댓글

  • 익명
  • 작성일
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;
    }
};

나무토끼님의 댓글

  • 익명
  • 작성일
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
        
전체 94 / 3 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 652 명
  • 오늘 방문자 4,092 명
  • 어제 방문자 7,431 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,542 명
알림 0