Có một thuật toán để xác định các vùng màu liền kề trong lưới không?

Question

Cho một lưới cơ bản (như một mảnh giấy vẽ), trong đó mỗi ô được điền một cách ngẫu nhiên với một trong các màu n, có một thuật toán đã thực hiện và thử nghiệm có thể cho tôi biết những vùng tiếp giáp nào (nhóm ô cùng một màu sắc được tham gia ở bên cạnh) có? Giả sử n là điều gì đó hợp lý, như 5.

Tôi có một số ý tưởng, nhưng tất cả đều cảm thấy không hiệu quả khủng khiếp.

Answer 1

Thuật toán tốt nhất có thể là O (số ô) và không liên quan đến số lượng màu. Điều này có thể đạt được bằng cách duyệt qua các ô và mỗi khi bạn truy cập vào một ô chưa được đánh dấu là đã truy cập, hãy thực hiện chuyển đồ thị để tìm tất cả các ô tiếp giáp trong vùng đó, sau đó tiếp tục lặp lại.

Edit:

Dưới đây là một ví dụ mã giả đơn giản của một tìm kiếm theo chiều sâu, đó là một cách dễ dàng để thực hiện thuật toán duyệt đồ thị:

function visit(cell) { 
    if cell.marked return 
    cell.marked = true 
    foreach neighbor in cell.neighbors { 
     if cell.color == neighbor.color { 
      visit(neighbor) 
     } 
    } 
} 

Answer 2

Bạn có thể thử đổ đầy lũ trên mỗi ô vuông. Khi lũ lụt lan rộng, ghi lại các ô vuông trong một mảng hoặc một thứ gì đó, và tô màu chúng trong một màu không sử dụng, nói -1.

Answer 3

Các bài viết trên Wikipedia về điền lũ có thể có ích đối với bạn ở đây : http://en.wikipedia.org/wiki/Flood_fill

Answer 4

Ngoài câu trả lời đệ quy đệ quy, bạn có thể sử dụng một chồng nếu đệ quy là quá chậm:

function visit(cell) { 
    stack = new stack 
    stack.push cell 

    while not stack.empty { 
     cell = stack.pop 
     if cell.marked continue 
     cell.marked = true 
     foreach neighbor in cell.neighbors { 
      if cell.color == neighbor.color { 
       stack.push neighbor 
      } 
     } 
    } 
} 

Answer 5

Union-find cũng sẽ hoạt động ở đây. Thật vậy, bạn có thể xây dựng câu hỏi của mình như một vấn đề về đồ thị: các đỉnh là ô lưới và hai đỉnh liền kề nếu ô lưới của chúng có cùng màu. Bạn đang cố gắng tìm các thành phần được kết nối.

Cách bạn sử dụng cấu trúc dữ liệu kết hợp tìm kiếm như sau: đầu tiên tạo cấu trúc dữ liệu kết hợp với nhiều phần tử khi bạn có ô. Sau đó lặp lại qua các ô và union hai ô liền kề nếu chúng có cùng màu. Cuối cùng, chạy find trên mỗi ô và lưu trữ phản hồi. Các ô có cùng số find nằm trong cùng một vùng màu liền kề nhau.

Answer 6

Nếu bạn muốn kiểm soát hạt mịn hơn một chút, bạn có thể nghĩ đến việc sử dụng thuật toán A* và sử dụng phương pháp phỏng đoán để bao gồm các ô màu tương tự.