← 返回题目列表

AtCoder · tessoku_book_bq

A69. 二分匹配

中文机器翻译题面 查看原题

配点: 1000 点

注意

根据本书的版本,书中的输入示例可能不正确。请参阅勘误表。

問題文

信息高中一年级A班 有 N 学生, 它们的编号最大为1 减去 N 。还有教室座位 N 可用,1 减去 N 。
好吧,今天我们要在课堂上换座位。你会得到一个愿望,比如“〇〇同学视力不好,所以前一个比较好。”找出你能满足的最多人数。

制約

  • 1 \leq N \leq 150
  • N 是一个整数
  • C_{i,j} 是 您也可以写 # 或 至少 . 是

入力

输入是按以下格式从标准输入给出的。
生徒 i 是座位 如果可以坐 j 如果你能坐进去 C_{i,j}= # ,否则 输出 C_{i,j}= . 。 对于

N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}

出力

请输出你最多可以实现多少人的愿望。


入力例 1

5
#....
#.#..
....#
....#
...##

出力例 1

4