Mã sơn MS được hỏi trong một cuộc phỏng vấn

Question

Tôi đã có một cuộc phỏng vấn hôm nay và đã được hỏi câu hỏi này!

mã chương trình MS Paint. Vùng N * N pixel. cho điểm ảnh và màu sắc, thay đổi màu theo pixel thành màu mong muốn và nếu các pixel liền kề có cùng màu thay đổi chúng.

tôi tiếp cận nó bằng cách nói rằng tôi sẽ lấy một mảng n * n và sẽ kiểm tra pixel được đưa ra và di chuyển đến điểm liền kề. ví dụ pixel được đưa ra là x, yi trước tiên sẽ kiểm tra màu trong x, y trong mảng và tìm kiếm tiếp theo (x + 1, y + 1), (x + 1, y), (x, y + 1), (x-1, y), (x-1, y-1) ....

nhưng người phỏng vấn không hài lòng có thể ai đó gợi ý cho tôi một cách khác bằng thuật toán tốt hơn .. có không gian tốt hơn và thời gian phức tạp!

Answer 1

Người phỏng vấn có thể yêu cầu điền vào lũ lụt, điều này không thể thực hiện với cách tiếp cận đơn giản như vậy.

Nếu điều này tràn ngập, đường chéo không được tính là liền kề.

Đổ tràn ngập lụt đơn giản nhất là một cuộc gọi đệ quy trên mỗi điểm ảnh liền kề trên mảng. Sử dụng cách đơn giản trên một lưới lớn là rất có khả năng chạy ra khỏi ngăn xếp.

Cách thích hợp là để enqueue vị trí bắt đầu, sau đó dequeue, kiểm tra xem màu pixel vẫn là nguồn màu, và quét trái và phải điền như bạn đi, và enqueue tất cả các điểm ảnh trên và dưới. Tiếp tục cho đến khi hàng đợi được thoát.

Answer 2

Thuật toán bạn đang nói đến được gọi là điền vào số . Các cách tiếp cận nổi tiếng được thảo luận tại Wikipedia.

Answer 3

Bạn có thể sử dụng thuật toán DFS để giải quyết vấn đề này. Với pixel (xi, yi), Bạn luôn có thể tạo biểu đồ sao cho nút pixel (xi-1, yi-1), (xi-1, yi), (xi, yi + 1), (xi + 1, yi), (xi + 1, yi-1), (xi + 1, yi + 1), (xi-1, yi + 1) và (xi, yi-1) làm nút pixel liền kề với (xi, yi) . Thực hiện DFS bắt đầu từ nút (xi, yi) tô màu từng nút trong đường dẫn và quay lại khi bạn nhấn nút màu khác nhau. DFS có độ phức tạp thời gian tốt của O (V + E).