6801 棋盘覆盖 0x60「图论」例题
描述
给定一个N行N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。N≤100。
输入格式
第一行为n,t(表示有t个删除的格子)
第二行到t+1行为x,y,分别表示删除格子所在的位置
x为第x行,y为第y列,行列编号从1开始。
输出格式
一个数,即最多能放的骨牌数
样例输入
8 0
样例输出
32
给定一个N行N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。N≤100。
第一行为n,t(表示有t个删除的格子)
第二行到t+1行为x,y,分别表示删除格子所在的位置
x为第x行,y为第y列,行列编号从1开始。
一个数,即最多能放的骨牌数
8 0
32