CONVEX - Hình giả lồi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Cho một lưới gồm n dòng m cột, trong đó mỗi ô được tô màu đen hoặc màu trắng. Từ một ô bất kỳ ta có thể đi sang bốn ô liền kề trên, dưới, trái, phải. Ta định nghĩa một đường đi màu đen là đường đi mà có ô đầu, ô cuối và các ô trung gian đều là các ô màu đen.

Ta gọi tập hợp các ô màu đen trong lưới là hình lồi nếu giữa hai ô màu đen bất kỳ tồn tại một đường đi màu đen mà chỉ đổi hướng tối đa một lần.

Hình lồi                           Hình không lồi

Từ lưới n dòng m cột ban đầu, hãy viết chương trình xác định xem các ô màu đen có phải là hình lồi hay không.

Dữ liệu nhập:

- Dòng đầu tiên lưu hai số nguyên nm (1 ≤ n, m ≤ 50) — là kích thước của lưới.

- Trong n dòng tiếp theo mỗi dòng chứa m số 0 hay 1, mỗi số cách nhau một khoảng trắng. Số 0 biểu diễn ô màu trắng và số 1 biểu diễn ô màu đen trong cột tương ứng. Dữ liệu vào bảo đảm có ít nhất một ô màu đen.

Dữ liệu xuất

- In ra YES nếu lưới là hình lồi, NO nếu lưới không phải hình lồi.

Ví dụ

  • input
    4 4
    0 0 1 0
    0 1 1 1
    1 1 1 1
    0 1 1 0
    output
    YES
  • input
    4 4
    0 1 1 0
    0 1 1 0
    0 1 0 0
    0 1 1 0
    output
    NO
Back to Top