P1524 Cross-Stitch

Archaeologists discovered a piece of cloth with needlework called "cross-stitch," where the thread alternates between the two sides of the cloth.

The cloth is an $n \times m$ grid. The thread can pass from one side of the cloth to the other only at the grid vertices. Each segment of thread covers one of the two diagonals of a unit cell, and during stitching, two consecutive segments within a single stitch must lie on opposite sides of the cloth. Given the patterns on both sides of the cloth (solid lines indicate a thread on this side, dashed lines indicate a thread on the opposite side), determine the minimum number of stitches needed to complete the embroidery. A stitch is a single embroidery process during which the needle does not leave the fabric. 

The first line contains two numbers $N$ and $M$ ($1 \le N, M \le 200$). The next $N$ lines each contain $M$ characters describing the front side. The following $N$ lines each contain $M$ characters describing the back side. Each cell is represented as follows: - $\verb!.!$ means empty. - $\verb!/!$ means a thread from the top-right corner to the bottom-left corner. - $\verb!\!$ means a thread from the top-left corner to the bottom-right corner. - $\verb!X!$ means the two diagonals cross.

Output a single integer, the minimum number of stitches required.

Translated by ChatGPT 5