المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۲:سوال ۱۱

پوشش مستطیلی

یک ماتریس از ارقام ۰ و ۱ داده شده است.

برنامه‌ای بنویسید که با کم‌ترین تعداد مستطیل، تمام ۱ های ماتریس را بپوشاند.

ورودی

در سطر اول ورودی به ترتیب تعداد سطرها $(m)$ و تعداد ستون‌ها $(n)$ ماتریس نوشته شده‌اند $(m,n\leq 50)$ و در هر یک از $m$ سطر بعد، $n$ عضو از یک سطر ماتریس با فاصله از هم آمده‌اند.

خروجی

در فایل خروجی در یک سطر تعداد مستطیل‌ها و در سطرهای بعد، در هر سطر مختصات گوشه‌ی بالا سمت چپ و پایین سمت راست هر مستطیل را بنویسید. مختصات گوشه‌ی بالا سمت چپ ماتریس را $(1,1)$ فرض کنید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 6
1 1 0 1 1 0
1 1 1 1 1 1
0 1 1 1 1 1
0 0 0 1 1 0
3
1 1 2 2
2 2 3 6
1 4 4 5

ابزار صفحه