#P1257. Cross-stitch.

    ID: 258 远端评测题 2000ms 10MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图结构二分图数据结构Ural Collegiate Programming Contest 1999

Cross-stitch.

本题没有可用的提交语言。

题目描述

考古学家发现了一块带有刺绣的布料。这种刺绣是由多根线组成的十字绣,遵循以下规则:

  1. 布料由方形网格组成
  2. 每个针脚覆盖网格单元格的一条对角线
  3. 针脚可以位于布料的正反两面,但每个针脚只在一面
  4. 每个单元格的每条对角线在每个面上最多只能有一个针脚
  5. 每根线由多个针脚组成,这些针脚交替出现在布料的两面
  6. 针只能通过网格顶点穿过布料

给定一个刺绣图案,要求计算制作该图案所需的最少线数。

输入格式

  • 第一行:网格的行数N和列数M(1≤N,M≤200)
  • 接下来2N行:前N行表示正面图案,后N行表示反面图案
  • 每个字符表示一个单元格的状态:
    • ".":空白
    • "/"或"":针脚
    • "X":正反两面都有针脚

输出格式

  • 一个整数:制作图案所需的最少线数

示例输入

输入:
4 5
.....
.\...
..\..
.....
.....
....\
.\X..
.....

示例输出

4