İnək Akademiyası III#11233
Fermer Con, Bessi və onun dostlarına kömək etmək üçün bir otlaq açdı.
Conun otlağı böyük bir 2D kvadrat hüceyrələr şəbəkəsi kimi təsəvvür edilə bilər. Hər bir hüceyrə aşağıdakı kimi işarələnir:
C əgər hüceyrədə inək varsa
G əgər hüceyrədə ot varsa
. əgər hüceyrədə nə inək, nə də ot varsa
İki fərqli inəyin dost olması üçün, onlar üfüqi və ya şaquli qonşu olan otlu bir hüceyrədə görüşməlidirlər. Bu görüş zamanı onlar həmin hüceyrədəki otu yeyirlər, buna görə də başqa bir inək cütü artıq bu hüceyrəni görüş yeri kimi istifadə edə bilməz. Hər hansı bir inək bir neçə başqa inəklə dost ola bilər, lakin heç bir inək cütü bir dəfədən çox görüşüb dost ola bilməz.
Con ümid edir ki, çoxlu inək cütləri dost olacaq. Dost ola biləcək inək cütlərinin maksimum sayını müəyyən edin.
Birinci sətir n və m (n, m ≤ 1000) ehtiva edir.
Növbəti n sətirin hər biri otlağı təsvir edən m simvoldan ibarətdir.
Dost ola biləcək inək cütlərinin maksimum sayını müəyyən edin.
Əgər biz i sətirində və j sütununda olan inəyi koordinatlarla (i, j) işarələsək, bu nümunədə (1, 2), (1, 5), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 3) və (4, 5) koordinatlarında inəklər var. 4 inəyin dost olması üçün bir yol belədir:
(2, 2) və (3, 3) koordinatlarında olan inəklər (3, 2) koordinatında olan otu yeyirlər.
(2, 2) və (2, 4) koordinatlarında olan inəklər (2, 3) koordinatında olan otu yeyirlər.
(2, 4) və (3, 3) koordinatlarında olan inəklər (3, 4) koordinatında olan otu yeyirlər.
(2, 4) və (1, 5) koordinatlarında olan inəklər (2, 5) koordinatında olan otu yeyirlər.
Nümunə 1