+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- > *کِوین* جدیدا با کار دریا‌نوردی آشنا شده‌است. او در حال سفر در دریایی بزرگ است که مسئله‌ای به ذهنش می‌رسد... دریایی که *کِوین* در آن قرار دارد جدولی از چهار طرف نامتناهی است، ولی ما تنها در مورد یک زیرجدول $n$ در $m$ از آن اطلاع داریم و می‌دانیم که بجز خشکی‌های داخل این زیر‌جدول، ‌در این دریا خشکی دیگری وجود ندارد. برای درک بهتر مسأله‌ی او ابتدا تعاریف مورد نیاز مساله‌اش را بیان می‌کنیم: + خانه‌های مجاور هر خانه تمام خانه‌هایی اند که حداقل یک را‌ٔس مشترک با‌ آن دارند. هر خانه در جدول ۸ خانه مجاور دارد. + *جزیره* به مجموعه‌ای ماکسیمال (یعنی هیچ خانه‌ی خشکی‌ای وجود ندارد که مجاور حداقل یکی از خانه‌های آن باشد و عضوی‌ از مجموعه نباشد) از خانه‌های خشکی است که همبند (بین هر دو خانه‌ای از آن مسیری شامل خانه‌های خشکی وجود دارد) است. + یک *مسیر دریایی* به دنباله‌ای از خانه‌های **آبِ** مجاور گفته‌ می‌شود که دو خانه‌ی خشکی را به هم وصل می‌کنند. + اگر بین دو *جزیره* یک *مسیر دریایی* وجود داشته باشد آن دو جزیره *دوست دریایی* یکدیگر نامیده می‌شوند. + به دنباله‌ای از تعدادی جزیره دو به دو متمایز که هر دو *جزیره* متوالی از آن *دوست دریایی* یکدیگر باشند *مسافرت* گفته می‌شود. *کِوین* می‌خواهد از هر کدام از جزیره‌های این دریا **دقیقا** یک‌بار دیدن بکند و تمام کالاهای موجود را جمع‌آوری کند. او می‌خواهد که این کار در کمترین تعداد *مسافرت* ممکن انجام شود. به او کمک کنید که این مسئله‌ را حل کند. # ورودی ورودی شامل یک خط است که در آن دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است. $$1 \le n,m \le 1 \ 000$$ سپس یک جدول $n$ در $m$ که از `.` یا `#` تشکیل شده است داده می‌شود. `.` نشان دهنده آب و `#` نشان دهنده خشکی است. # خروجی در تنها خط خروجی تعداد *مسافرت*های لازم را خروجی‌‌دهید. ## ورودی نمونه ۱ ``` 5 5 #.#.# ..#.. ##### ..#.. #.#.# ``` ## خروجی نمونه ۱ ``` 1 ``` توضیح: $*$ مسیر مسافرت را نشان می‌دهند: ``` ......... ..***.... ..#.#*#*. ....#..*. ..#####*. ....#..*. ..#.#*#*. ..****... ......... ``` ## ورودی نمونه ۲ ``` 7 17 ###############.# #.#####.#####.#.. #.#...#.#...#.#.. #.#.#.#.#.#.#.#.. #.#...#.#...#.#.. #.#####.#####.#.. ###############.. ``` ## خروجی نمونه ۲ ``` 2 ``` توضیح: $*$ مسیر مسافرت را نشان می‌دهند: ``` ..................... ..................... ..###############*#*. ..#.#####.#####.#.... ..#.#.*.#.#...#.#.... ..#.#.#.#.#.#*#.#.... ..#.#...#.#...#.#.... ..#.#####.#####.#.... ..###############.... ..................... ..................... ```

حل سؤال در بانک سؤالات