فهرست مندرجات
تخته‌ی مدار الکتریکی
یک تخته‌ی مدار داریم که به صورت یک جدو مستطیلی است و سیم‌ها به صورت افقی یا عمودی رئوس مجاور را به هم وصل می‌کنند. (دقت کنید رئوس روی گره‌های جدول قرار دارند.) یک تخته مدار همبند است اگر از هر راس به هر راس دیگری مسیر وجود داشته باشد. یک تخته مدار داده شده است، که سیم‌ها بعضی از رئوس مجاور را به هم متصل کرده‌اند. ما می‌خواهیم تعدادی سیم اضافه کنیم که تخته مدار ما همبند شود. هزینه‌ی هر سیم عمودی ۱ و هزینه‌ی هر سیم افقی ۲ است.
شما باید برنامه‌ای بنویسید که کم‌ترین هزینه برای همبند شدن تخته مدار را بیابد.
برنامه‌ی شما باید ۳ زیرمسئله را حل کند.
- تعداد سیم‌ها در همبند کردن با کم‌ترین هزینه را محاسبه کند.
- مقدار کم‌ترین هزینه‌ی لازم را محاسبه کند.
- لیستی از سیم‌هایی که باید اضافه شود تا کم‌ترین هزینه را برای همبند کردن مدار داشته باشد را ارئه دهد.
ورودی
در سطر اول فایل ورودی دو عدد $M$ و $N$ داده شده است. که به ترتیب تعداد سطرها و ستون‌های جدول را مشخص می‌کند. رئوس مدار با مختصاتشان مشخص می‌شوند: راس بالا سمت چپ جدول $(1,1)$ را دارد و راس پایین سمت راست مختصات $(N,M)$.
در $N$ سطر بعدی در هر سطر $M$ عدد داده شده است. عدد سطر $i$ ام و ستون $j$ ام مشخص‌کننده‌ی سیم بین رئوس $(i,j)$ و $(i+1,j)$ و همچنین سیم بین رئوس $(i,j)$ و $(i,j+1)$ است به این صورت:
- ۰ یعنی هیچ‌کدام از جفت راس‌های $(i,j)$ و $(i+1,j)$ همچنین $(i,j)$ و $(i,j+1)$ با سیم به هم مربوط نیستند.
- ۱ یعنی فقط جفت راس‌های $(i,j)$ و $(i+1,j)$ با سیم به هم متصل هستند.
- ۲ یعنی فقط جفت راس‌های $(i,j)$ و $(i,j+1)$ با سیم به هم متصل هستند.
- ۳ یعنی هر دو جفت راس‌های $(i,j)$ و $(i+1,j)$ همچنین $(i,j)$ و $(i,j+1)$ با سیم به هم متصل هستند.
دقت کنید که هر ۴ مقدار برای هر راسی معتبر نیست مثلا برای خانه‌ی $(N,M)$ فقط عدد ۰ معتبر است. در ضمن $1\leq M,N \leq 100$.
خروجی
در سطر اول فایل خروجی شما باید دو عدد $K$ و $V$ را بنویسید. که $K$ جواب زیرمسئله‌ی اولی یعنی همان تعداد سیم‌های جدیدی است که باید کشیده شود تا مدار همبند شود و $V$ همان کم‌ترین هزینه‌ی لازم است. در ادامه‌ی فایل شما باید در $K$ سطر لیستی از سیم‌های لازم را به هر ترتیبی که دوست دارید بنویسید. در هر سطر باید ۳ عدد نوشته شود $i,j,d$ که $(i,j)$ متخصات راس و $d$ یکی از دو مقدار ۱ یا ۲ را به خود می‌گیرد. ۱ یعنی سیم جدید از راس $(i,j)$ به $(i+1,j)$ کشیده شده است و ۲ یعنی این سیم از راس $(i,j)$ به $(i,j+1)$ کشیده شده است.
ورودي و خروجي نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
