P5030 长脖子鹿放置
题目背景
众周所知,在西洋棋中,我们有城堡、骑士、皇后、主教和长脖子鹿。
题目描述
如图所示,西洋棋的“长脖子鹿”,类似于中国象棋的马,但按照“目”字攻击,且没有中国象棋“别马腿”的规则。(因为长脖子鹿没有马腿)

给定一个$N * M$,的棋盘,有一些格子禁止放棋子。问棋盘上最多能放多少个不能互相攻击的长脖子鹿。
输入格式
无
输出格式
无
说明/提示
**重要提示:请务必思考对图的遍历顺序对运行速度的影响**
对于$10$%的数据, $1 ≤ N,M ≤ 5$
对于$30$%的数据, $1 ≤ N,M ≤ 10$
对于$60$%的数据, $1 ≤ N,M ≤ 50$
对于$80$%的数据, $1 ≤ N,M ≤ 100$
对于$100$%的数据,$1 ≤ N,M ≤ 200$
数据已修正,有一些错误的算法(包括部分题解)将不能通过本题。
感谢@Alpha 指出问题