Optimal kəsmə

Polykarpın n \times m hüceyrədən ibarət bir düzbucaqlı şəbəkəsi var, burada hər bir hüceyrədə bir kiçik latın hərfi yazılıb.

İki hüceyrə bağlı sayılır, əgər onlar bir tərəfi paylaşır və hər ikisində eyni hərf yazılıbsa.

Monoxromatik bölgə odur ki, bir neçə hüceyrənin qrupu, burada istənilən iki hüceyrə ya birbaşa, ya da digər hüceyrələr ardıcıllığı vasitəsilə bağlıdır və qrupa daha bir hüceyrə əlavə etmək mümkün deyil ki, bu xassə pozulmasın.

Hüceyrənin tərəfi daxili sayılır, əgər o, şəbəkənin iki müxtəlif hüceyrəsini ayırırsa.

Yol isə fərqli daxili tərəflər ardıcıllığıdır, burada ardıcıl tərəflərin hər biri hansısa hüceyrənin küncündə rastlaşır.

Polykarp bütün monoxromatik bölgələri bir-birindən ayırmaq istəyir. Hər kəsik bir yol boyunca aparıla bilər — yəni, əvvəllər kəsilməmiş bir sıra daxili tərəfləri düz bir yol şəklində kəsə bilər. Bütün kəsiklərdən sonra heç bir monoxromatik bölgə parçalanmamalıdır.

Polykarp bunu başarmaq üçün ən az neçə kəsik etməlidir?