A69 - Bipartite Matching Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

注意

書籍の版によっては、書籍内の入力例が正しくない場合があります。正誤表を参照してください。

問題文

情報高校の 1 年 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