عدالت قضایی برره


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

می‌دانیم عدالت قضایی جایگاه ویژه‌ای در میان اهالی برره دارد.

کَیانوش، نظام و کیوون به ترتیب به جرم اخلال در نظم عمومی، کشیدن گرد نخود و زورگیری در ژاندارمری برره دست‌گیر شده‌اند.

نقشه‌ی زندان به شما داده شده است. زندان به شکل یک جدول n×mn \times m است و از سه سلول تشکیل شده است. سلول مجموعه‌ای از بلوک‌های خالی از جدول است که دو به دو به هم مسیر دارند (یک مسیر دنباله‌ای از خانه‌هاست که هر دوتای پشت سر هم با هم مجاورند، منظور از مجاورت در این سوال مجاورت ضلعی‌ست). بقیه‌ی زندان با بلوک‌های گلی پر شده است. این سه زندانی می‌خواهند با تخریب بلوک‌های گلی مجاور سلول‌های خود، هر ۳ سلول را به یک دیگر متصل کنند و با هم برای فرار نقشه بریزند. بدیهی‌ست وقتی یک بلوک گلی خراب شود ممکن است بلوک‌های گلی دیگری در دسترس قرار گیرد. کمترین تعداد بلوک‌های گلی‌ای که باید خراب کنند را بیابید.

ورودی🔗

در خط اول nn و mm داده شده است که به ترتیب تعداد سطرها و ستون‌های زندان ژاندارمری برره را نشان می‌دهد. در هر یک از nn سطر بعدی mm کاراکتر آمده است که X نشان‌دهنده‌ی بخشی از یک سلول و . نشان‌دهنده‌ی یک دیوار است. 1n,m501 \le n, m \le 50

خروجی🔗

کمترین تعداد دیواری که باید خراب کنند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....
Plain text

خروجی نمونه ۱🔗

4
Plain text

توضیح نمونه ۱:🔗

مطابق شکل زیر اگر بلوک‌های گلی‌ای که با * مشخص شده اند را خراب کنند تمامی سلول‌ها به هم متصل می‌شوند.

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....
Plain text