thảo luận Leetcode mỗi ngày

Chạy cái khoảng cách tính distance từ mỗi đỉnh tới theft O(n^4) chết ngắc, phải tối ưu lại bằng BFS lol
Mình tính ra chỉ tầm khoảng (n - k)^2*k^2 cho mỗi lần tính mà vẫn chết.
Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
     
        dist = [[float('inf')] * n for _ in range(n)]
        queue = deque()
     
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i, j))
                    dist[i][j] = 0
     
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
     
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == float('inf'):
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
     
        def isGood(safeness):
            if dist[0][0] < safeness or dist[n - 1][n - 1] < safeness:
                return False
         
            visited = set()
            queue = deque([(0, 0)])
            visited.add((0, 0))
         
            while queue:
                r, c = queue.popleft()
                if r == n - 1 and c == n - 1:
                    return True
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited and dist[nr][nc] >= safeness:
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return False

        left, right = 0, n
        ans = 0
     
        while left <= right:
            mid = (left + right) // 2
            if isGood(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
     
        return ans
TLE đoạn tính distance, sửa lại qua tính BFS là ok
Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        thief = []
        directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        dp = [[inf for _ in range(n)] for _ in range(n)]                
        if grid[0][0] == 1 or grid[n -1][n - 1] == 1:
            return 0

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    thief.append([i, j])

        for i in range(n):
            for j in range(n):
                for row, column in thief:
                    dp[i][j] = min(dp[i][j], abs(row - i) + abs(column - j))

        def good(row, column, target, seen):
            if row == 0 and column == 0 and dp[row][column] < target:
                return False
               
            if row == n - 1 and column == n - 1:
                return True

            for dx, dy in directions:
                nx, ny = dx + row, dy + column
                if 0 <= nx < n and 0 <= ny < n and not (nx, ny) in seen and dp[nx][ny] >= target:
                    seen.add((nx, ny))
                    if good(nx, ny, target, seen):
                        return True

            return False

        left = 0
        right = n
        ans = 0
        while left <= right:
            mid = left + (right - left)//2
            if good(0, 0, mid, set([0, 0])):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans
 
Last edited:
Violet_7 said:
Moẹ thằng leetcode cho quả n to vãi, làm đúng complexity rồi phải tối ưu thêm nữa ms pass :sweat: , thằng Python run nhanh nhất mất 2s :sweat:

Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def get_safeness_factors():
            queue = deque()
            safeness_factors = [[0] * n for _ in range(n)]
          
            for row in range(n):
                for col in range(n):
                    if grid[row][col] == 1:
                        queue.append((row, col, 0))

            while queue:
                curr_row, curr_col, curr_safeness = queue.popleft()

                for row_dir, col_dir in dirs:
                    next_row = curr_row + row_dir
                    next_col = curr_col + col_dir
                    if not (0 <= next_row < n and 0 <= next_col < n):
                        continue

                    if grid[next_row][next_col] == 1:
                        continue

                    next_safeness = curr_safeness + 1
                    safeness_factors[next_row][next_col] = next_safeness
                    queue.append((next_row, next_col, next_safeness))
                    grid[next_row][next_col] = 1

            return safeness_factors

        safeness_factors = get_safeness_factors()

        def can_have_valid_path(min_safeness_factor):
            if safeness_factors[0][0] < min_safeness_factor:
                return False

            visited_cells = set((0, 0))
            queue = deque([(0, 0)])

            while queue:
                curr_row, curr_col = queue.popleft()
                if curr_row == curr_col == n - 1:
                    return True

                for row_dir, col_dir in dirs:
                    next_row = curr_row + row_dir
                    next_col = curr_col + col_dir
                    if not (0 <= next_row < n and 0 <= next_col < n):
                        continue
                    if (next_row, next_col) in visited_cells:
                        continue
                    if safeness_factors[next_row][next_col] < min_safeness_factor:
                        continue
                  
                    visited_cells.add((next_row, next_col))
                    queue.append((next_row, next_col))
          
            return False

        left = 0
        right = 2 * n
        result = 0

        while left <= right:
            mid = (left + right) // 2
          
            if can_have_valid_path(mid):
                left = mid + 1
                result = mid
            else:
                right = mid - 1
      
        return result
Click to expand...
Cái bài của thằng top 1 mình ko hiểu lắm mai fence, giải thích mình đoạn nó xài min heap đi từ thằng distance [n-1, n-1] với :ah:
 
Aluminum21 said:
Bài bữa nay là bài làm toy tạch pv, sau đó cay mới bắt đầu làm leetcode. Hồi đó nó cho nửa tiếng hay 45' gì quên toi rồi. :censored: :what:
Click to expand...
pv ở đâu mà hỏi khó thế fen
u3720e4.png
 
Bài hôm nay khó hơn so với medium bình thường.

Ngồi nghĩ ra chỗ dùng BFS để tính distance. Đoạn tìm max nghĩ k ra, phải coi sol để lấy keyword rồi tự implement. :ah:
Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        def fill(q):
            if not q:
                return
            next_q = []
            for i, j in q:
                for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 0:
                        continue
                    grid[x][y] = grid[i][j] + 1
                    next_q.append((x,y))
            fill(next_q)
        fill([(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 1])

        q = []
        heapq.heappush(q, (-grid[0][0], 0, 0))
        grid[0][0] = 0
        while q:
            val, i, j = heapq.heappop(q)
            if i == len(grid) - 1 and j == len(grid[0]) - 1:
                return -val - 1
            for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:
                    continue
                heapq.heappush(q, (max(-grid[x][y], val), x, y))
                grid[x][y] = 0
        return 0
 
C++: 
constexpr int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};

using ia3 = array<int,3>;

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if (grid[0][0] || grid[m-1][n-1]) return 0;

        // precompute distance grid[i][j] is minimum distance from (i,j)
        // top-left to bottom-right
        grid[0][0] = 1e9;
        for (int i = 1; i < m; i++) grid[i][0] = grid[i][0] ? 0 : grid[i-1][0] + 1;
        for (int j = 1; j < n; j++) grid[0][j] = grid[0][j] ? 0 : grid[0][j-1] + 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = grid[i][j] ? 0 : min(grid[i-1][j], grid[i][j-1]) + 1;
            }
        }
        // bottom-right to top-left
        for (int i = m-2; i >= 0; i--) grid[i][n-1] = min(grid[i][n-1], grid[i+1][n-1] + 1);
        for (int j = n-2; j >= 0; j--) grid[m-1][j] = min(grid[m-1][j], grid[m-1][j+1] + 1);
        for (int i = m-2; i >= 0; i--) {
            for (int j = n-2; j >= 0; j--) {
                grid[i][j] = min(grid[i][j], min(grid[i+1][j], grid[i][j+1]) + 1);
            }
        }

        // dijkstra
        priority_queue<ia3,vector<ia3>> q; // max-heap of {cost,i,j}
        q.push({grid[0][0], 0, 0});
        while (!q.empty()) {
            auto [c, i, j] = q.top(); q.pop();
            if (grid[i][j] == -1) continue;
            grid[i][j] = -1;
            if (i == m-1 && j == n-1) return c;
            for (int k = 0; k < 4; k++) {
                int ii = i+di[k], jj = j+dj[k];
                if (ii < 0 || jj < 0 || ii == m || jj == n || grid[ii][jj] == -1) continue;
                int cc = min(c, grid[ii][jj]);
                if (cc) q.push({cc,ii,jj});
            }
        }

        return 0;
    }
};
 
Last edited:
Medium-hard

Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        def findMinThiefDist():
            q = deque()
            distance = [[0] * n for _ in range(n)]
            for row in range(n):
                for col in range(n):
                    if grid[row][col] == 1:
                        q.append((row, col))
            seen = set(q)
            while q:
                row, col = q.popleft()
                for neiRow, neiCol in (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1):
                    if neiRow < 0 or neiRow >= n or neiCol < 0 or neiCol >= n:
                        continue
                    if (neiRow, neiCol) in seen:
                        continue
                    seen.add((neiRow, neiCol))
                    distance[neiRow][neiCol] = distance[row][col] + 1
                    q.append((neiRow, neiCol))
            return distance

        n = len(grid)
        minThiefDist = findMinThiefDist()
        maxHeap = [(-minThiefDist[0][0], 0, 0)] # distance, row, col
        seen = set()

        while maxHeap:
            pathDist, row, col = heapq.heappop(maxHeap)
            pathDist = -pathDist
            if row == n - 1 and col == n - 1:
                return pathDist
            seen.add((row, col))
            for neiRow, neiCol in (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1):
                if neiRow < 0 or neiRow >= n or neiCol < 0 or neiCol >= n:
                    continue
                if (neiRow, neiCol) in seen:
                    continue
                newDist = min(minThiefDist[neiRow][neiCol], pathDist)
                heapq.heappush(maxHeap, (-newDist, neiRow, neiCol))
                seen.add((neiRow, neiCol))
 
Python: 
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        sourceQueue = deque()
        m, n = len(grid), len(grid[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    sourceQueue.append((i, j))
                    grid[i][j] = 0
                else:
                    grid[i][j] = -1
                
        while sourceQueue:
            lenQueue = len(sourceQueue)
            while lenQueue > 0:
                pos = sourceQueue.popleft()
                for d in dirs:
                    u, v = pos[0] + d[0], pos[1] + d[1]
                    if u < 0 or u >= m or v < 0 or v >= n:
                        continue
                    if grid[u][v] == -1:
                        grid[u][v] = grid[pos[0]][pos[1]] + 1
                        sourceQueue.append((u, v))
                lenQueue -= 1

        heap = [(-grid[0][0], 0, 0)]
        grid[0][0] = -1
        result = 0

        while heap:
            safeness, i, j = heapq.heappop(heap)
            if i == m - 1 and j == n - 1:
                result = -safeness
                break
            
            for d in dirs:
                u, v = i + d[0], j + d[1]
                if u < 0 or u >= m or v < 0 or v >= n:
                    continue
                if grid[u][v] != -1:
                    heapq.heappush(heap, (-min(-safeness, grid[u][v]), u, v))
                    grid[u][v] = -1
        return result
 

Similar threads

nhbin
kiến thức Kèo Watch to earn 5p mỗi ngày $EVERY gọi vốn $60M từ A16Z, Coinbase, DragonFly
Replies
0
Views
88
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
621
heocon0123
heocon0123
MasterchiefsReborn
Sinh viên than kiến tập mà làm việc không kịp ăn
2 3
Replies
48
Views
3K
OneThing
OneThing
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
158
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
424
truonggiang!
T

Share this page

Back
Top