Duyệt miền liên thông

#1

Em xin hỏi về áp dụng thuật toán loang (BFS) hoặc DFS đếm miền liên thông trong mảng nhị phân (các phần tử chỉ có giá trị 0 hoặc 1)?

Vấn đề em cần hỏi:
Làm thế nào để tìm đỉnh để bắt đầu duyệt?

Ví dụ:
1 0 0
0 0 0
0 0 1
Mảng này có 2 miền, nhưng làm sao để biết (0,0) và (1,1) là đỉnh thuộc 2 miền khác nhau?
Tức là, sau khi duyệt xong miền chứa (0,0) làm sao để biết (1,1) để duyệt tiếp?

Em cảm ơn nhiều!

#2 
for nút in tất_cả_các_nút:
    if nút chưa duyệt:
        dfs(nút)  # hoặc bfs(nút)
#3

Em rất cảm ơn anh HK boy nhiệt tình giúp đỡ và nhắc nhở.
Ý của em là xét miền liên thông 4 (để tránh nhầm lẫn sang liên thông 8 em đã sửa lại bài post).
Em nhận thấy phần duyệt nút anh HK boy đưa ra là duyệt các nút kề nút đã biết.
Ví dụ:
1 1 0
0 1 0
0 0 0
Ta biết (0,0) là 1 nút hợp lệ (trong trường hợp này, hợp lệ là nút có giá trị bằng 1) nên ta sẽ duyệt các nút kề hợp lệ (trong trường hợp này là (0,1) và (1,1) ) và tiếp tục như anh HK boy đã làm.
Tuy nhiên nếu ta có mảng sau:
? ? ?
? ? ?
? ? ?
Biết các giá trị của ? là 0 hoăc 1.
Ta muốn bắt đầu duyệt từ vị trí nào thì làm thế nào vậy?

#5

Bắt đầu duyệt từ đâu cũng được. Trong bảng thì:

for hàng i:
    for cột j:
        if ô(i, j) hợp lệ và chưa duyệt:
            dfs(i, j)  # hoặc bfs(i, j)

Mình mới đọc lại đề của bạn. Sorry vì mình đọc chưa kĩ.
Theo đề của bạn, ta có thể thấy rằng: từ ô (i, j) có thể đi đến 4 ô kề cạnh: (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1), trừ những ô không thể vào. Bạn có thể tạo 2 mảng:

dx[] = {0, 0, -1, 1};
dy[] = {-1, 1, 0, 0};

Khi duyệt tới các ô có thể từ ô i, j:

dfs(i, j):
    for k = 0 -> 3:
        if ô (i + dx[k], j + dy[k]) hợp lệ và chưa duyệt:
            dfs(i + dx[k], j + dy[k])  # hoặc bfs

Thuật toán này là thuật toán loang. Bạn có thể tìm dựa theo gợi ý của mình.

1 Like
#6

nên sử dụng bdf khử đệ qui đi bạn.

#7

Cái gì thế bạn?

Thực ra BFS với DFS có độ phức tạp đều O(n) hết. BFS có mất thêm O(n) bộ nhớ. Mà quan tâm làm gì cho mệt.

#8

DFS cũng có O(độ cao cây) mem :slight_smile: nếu không thì không thể nói chuyện “quay lại” được.

DFS có thể bị lạc vĩnh viễn với cây vô hạn :smiley: còn BFS (O(cái cây)) mem) “từ từ” sẽ tìm ra, nếu có.

1 Like
#9

Ah, ý mình là xài bằng phương pháp khử đệ qui ấy mà, cả BFS và DFS, lúc xưa đi học phần này mình hay chơi khử đệ qui, dùng đệ qui khó control lắm

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?