isTadpole

Codelearn quyết định tạo ra một trình nhận dạng hình ảnh tự động xác định đối tượng trong ảnh dựa trên các đường viền của nó. Hệ thống nhận dạng chính đã được triển khai và giờ chúng ta sẽ bắt đầu quá trình giảng dạy.

Hôm nay, chúng ta sẽ dạy chương trình nhận dạng các mẫu nòng nọc, điều đó đồng nghĩa với việc chúng ta cần phải thực hiện một chức năng mà khi đưa ra các ma trận kề thể hiện các đường viền, chức năng đó sẽ xác định xem đó có phải là con nòng nọc hay không.

Các đường viền của con nòng nọc sẽ bao gồm 2 phần: phần đầu là một vòng khép kín với các đỉnh n (n > 2), và một cái đuôi là một đường thằng đơn giản (có ít nhất một đỉnh) được nối với đầu. Đây là một ví dụ:

Cho một đường viền của đối tượng dưới dạng một đồ thị vô hướng được biểu thị bằng ma trận kề adj. Hãy kiểm tra xem nó có phải là nòng nọc hay không.

Ví dụ

Với

adj = [[false, true, true, false, false],
       [true, false, false, true, false],
       [true, false, false, true, false],
       [false, true, true, false, true],
       [false, false, false, true, false]]

đầu ra là
isTadpole(adj) = true.

Đồ thị đã cho trông như sau:

Đầu ra/Đầu vào

• [giới hạn thời gian chạy] 1.5 giây

• [đầu vào] Matrix of booleans adj

  Một ma trận kề vô hướng.

  Điều kiện tiền đề:
  3 < adj.length < 20,
  adj[i].length == adj.length.

• [đầu ra] boolean
  true nếu đường viền là nòng nọc, false nếu không phải.