宠物袋的最大宠物装载量：动态规划解法

小明的宠物袋
题目描述
小明拥有一个N×M的矩阵型宠物袋A,宠物袋的一个单元刚好可以装下一只宠物。
起初，宠物袋的某些单元已经放置了小明买的食物，这些单元将不能再用来装宠物。
现在小明准备去宠物商店购买宠物，并将购买的宠物放入宠物袋带回家。然而商店的宠物之间的关系一直不和，一旦两宠物放在相邻(上下左右)的单元，它们就会打起来。
小明想带尽可能多的宠物回家，同时也不希望宠物之间会打架。请你帮他算算，他最多可以带多少宠物回家。
输入描述
输入第1行包含两个整数N,M,表示小明宠物袋的大小。
接下来N行，每行包含M个数——aij,表示宠物袋该单元起初是否已被用来装东西(aij=1表示该单元已经装了食物，不能用来装宠物了；ai,j=0表示该单元可以用来装宠物)。
1≤N≤30,1≤M≤10,ai;j∈(0,1)。
输出描述
输出一行整数表示小明所能带走的最多宠物数。
输入输出样例
示例1
输入
23
1 Q θ
111
输出
1
运行限制
语言
最大运行时间
C++
1s
C<