D. Онцгой тор

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чамд $n × m$ хэмжээтэй тор өгөгдсөн ба зарим зангилаа нь хар, бусад нь цагаан байна. Үүнээс гадна энэ нь энгийн биш тор юм. Торны квадрат хэсэг бүрийн диогналиудыг будсан.

Доорх зураг бол $3 × 5$ хэмжээтэй торны жишээ юм. Торны дөрвөн зангилаа нь хар, үлдсэн $11$ зангилаа нь цагаан.

Чиний даалгавар бол өгөгдсөн торны гурвалжингуудыг тоолох юм:

  • булангуудыг цагаан хэсгүүд дээр тааруулна;
  • бүх талууд нь торны шугамын дагуу явна.(босоо эсвэл хэвтээ диогналиар);
  • хар зангилаа агуулсан тал байж болохгүй.

Оролт

Эхний мөрөнд $n$ ба $m$ $(2 ≤ n, m ≤ 400)$ хоёр бүхэл тоо оруулна. Дараагийн $n$ мөр бүр нь торыг тодорхойлсон $m$ тэмдэгтүүдийг агуулна (тэг ба нэг). Хэрвээ $i$-р мөрийн $j$-р тэмдэгт нь тэг бол хөндлөнгөөр $i$-р мөр, босоогоор $j$-р баганы зангилаа цагаан байна. Эсрэг тохиолдолд зангилааг хараар будна.

Хэвтээ шугам нь дээрээс доошоо нэгээс эхлэн дугаарлагдсан бол босоо шугам нь зүүнээс баруун тийш нэгээс эхлэн дугаарлагдсан.

Гаралт

Шаардсан гурвалжингийн тоо болох нэг бүхэл тоо хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 5
10000
10010
00001
Гаралт
20
Оролт
2 2
00
00
Гаралт
4
Оролт
2 2
11
11
Гаралт
0

Тэмдэглэл

Доорх зурагт улаан болон цэнхрээр гурвалжингуудыг харуулав. Эдгээр гурвалжин нь эхний жишээний шаардсан гурвалжин юм. Ногооноор будсан гурвалжингуудыг хүчингүйд тооцно. Учир нь бүх талууд нь торны шугамны дагуу яваагүй.

Сэтгэгдлүүдийг ачааллаж байна...