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