Như đã đề xuất trong tên của vấn đề, chúng ta nên nghĩ đến giải pháp liên quan đến biểu đồ và cụ thể hơn là về thuật toán Tìm kiếm theo chiều sâu trên chúng.
Để hiểu rõ hơn những gì chúng tôi cần phải nhận, hãy xem ví dụ được cung cấp.
______0Ma trận này có hai cái gọi là "vùng", một vùng chỉ lấy 1 ở góc dưới cùng bên trái, vùng còn lại lấy tất cả các vùng còn lại. Rõ ràng, cái lớn nhất là cái sau, vì vậy chúng tôi dự kiến sẽ trả về 5.
Lưu ý rằng hai ô 'sống' được coi là được kết nối nếu chúng có khoảng cách bằng một, theo chiều ngang, chiều dọc hoặc đường chéo.
Làm theo gợi ý, tôi đã triển khai giải pháp python của mình bằng cách áp dụng DFS trên từng ô trong ma trận.
____11. Kết quả được khởi tạo bằng 0, khi kết nối [] trả về giá trị cao hơn kết quả hiện tại, nó sẽ thay thế giải pháp tốt hơn hiện tại được tìm thấy.
Bây giờ mình chỉ cần viết hàm connect[]. Dựa trên DFS, nó sẽ gọi đệ quy chính nó để tìm kiếm tất cả các ô được kết nối với ô hiện tại. Biến thể nhỏ, nó sẽ trả về kích thước của nhóm. Vì lý do hiệu quả, tôi quyết định thực hiện nó một cách đột phá. Ma trận sẽ được sửa đổi để theo dõi các ô đã truy cập. Đây thường không phải là một ý tưởng hay, nhưng trong một vấn đề như thế này, chúng ta có thể chấp nhận nó.
______21. Nếu chúng ta đang bước ra khỏi ranh giới ma trận, thì không có gì để làm. Chỉ cần trả về số không.
2. Nếu ô hiện tại không "sống", nó không thuộc bất kỳ nhóm nào, trả về 0.
3. Nếu không, hãy tính nó cho nhóm hiện tại.
4. Đây là điểm mềm mà tôi đã nói ở trên. Thay vì theo dõi nút đã truy cập, tôi chỉ cần đặt nút đó thành "chết". Nó sẽ không gây hại cho thuật toán, vì chúng ta chỉ đếm mỗi nút một lần, tuy nhiên, người gọi có thể ngạc nhiên khi thấy ma trận của nó thay đổi.
5. Đi và truy cập tất cả các nút được kết nối với nút hiện tại. Hai vòng lặp for chọn các chỉ số trong ô liền kề hiện tại, "nếu" loại trừ ô hiện tại. Chúng tôi sẽ kiểm tra xem vị trí đã chọn có tham chiếu đến một nút được kết nối thực tế trong [1] và [2] hay không, sau đó áp dụng đệ quy.
Và thế là xong. Mã python đầy đủ và trường hợp thử nghiệm tôi đã sử dụng để giúp tôi tìm giải pháp có trên GitHub.
Xem xét một ma trận có hàng và cột, trong đó mỗi ô chứa a hoặc a và bất kỳ ô nào chứa a được gọi là ô đầy đầy đủ. Hai ô được cho là liên kết nếu chúng liền kề nhau theo chiều ngang, chiều dọc hoặc đường chéo;
Nếu một hoặc nhiều ô được điền cũng được kết nối, thì chúng tạo thành một vùng. Lưu ý rằng mỗi ô trong một vùng được kết nối với ít nhất một ô khác trong vùng nhưng không nhất thiết phải được kết nối trực tiếp với tất cả các ô khác trong vùng
Nhiệm vụ
Cho một ma trận, tìm và in số lượng ô trong vùng lớn nhất trong ma trận. Lưu ý rằng có thể có nhiều hơn một vùng trong ma trận.
Định dạng đầu vào
Dòng đầu tiên chứa một số nguyên, , biểu thị số hàng trong ma trận.
Dòng thứ hai chứa một số nguyên, biểu thị số cột trong ma trận.
Mỗi dòng của các dòng tiếp theo chứa các số nguyên được phân tách bằng dấu cách mô tả các giá trị tương ứng điền vào mỗi hàng trong ma trận.
Hạn chế
Định dạng đầu ra
In số ô trong vùng lớn nhất trong ma trận đã cho
đầu vào mẫu
4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
Đầu ra mẫu
5
Giải trình
Sơ đồ dưới đây mô tả hai vùng của ma trận;
X X 0 0 1 1 0 0
0 X X 0 0 1 1 0
0 0 X 0 0 0 1 0
1 0 0 0 X 0 0 0
Vùng thứ nhất có năm ô và vùng thứ hai có một ô. Vì chúng tôi muốn in số ô trong vùng lớn nhất của ma trận, chúng tôi in