P2172 [CTT] Tribal War

lanzerb’s tribe is in the northern part of Country A. Dissatisfied with the freezing weather, they plan to wage war toward the southern part of Country A to seize more territory.

Country A is an $M \times N$ matrix, where some cells are towns and some are uninhabited mountains and chasms. lanzerb divides his tribe into several armies, with the following rules: Each army may start from any town and can only advance downward, from top to bottom, without turning back. Along the way, they may pass only through towns, not through mountains and chasms. If a town has been visited by one army, no other army may visit that town again. Each army may stop at any town. All the armies move in a way similar to a knight in chess. However, while a knight moves in a $1 \times 2$ pattern, they move in an $R \times C$ pattern. Driven by ambition, lanzerb aims to unite the entire country, but limited manpower makes staffing difficult. Assuming each army successfully occupies all towns it passes through, please help lanzerb compute the minimum number of armies needed to unify the entire country.

The first line contains $4$ integers $M, N, R, C$, as described above. Then follow $M$ lines, each being a string of length $N$. If a character is `.` it denotes a town; if a character is `x` it denotes mountains and chasms.

Output a single integer, the minimum number of armies.

Constraints For $100\%$ of the testdata, $1 \le M, N \le 50$, $1 \le R, C \le 10$. Translated by ChatGPT 5