3492. [POJ 1084]破坏正方形

【题目描述】

给定一个“在由火柴棒拼成的n*n(n$\le$5)的网格图中去掉一些边”构成的图形（如下右图所示）。求至少再去掉多少根火柴棒，可以使得图形中不含有正方形（内部有其他火柴的大正方形也算），例如下右图中有5个正方形。

火柴编号如上图（左）所示。

【输入格式】

第一行一个整数T，表示T组数据。

接下来每组数据由两行组成：第一行包含一个自然数n，（n$\le$5），表示n*n网格，

第二行一个正整数k,即完整n*n网格中缺少的火柴棒数，接下来k个整数指定缺失火柴棒编号。注意，如果k等于零，那么输入网格是一个完整的n*n网格。

【输出格式】

每组数据输出一行，表示最少拿掉的火柴数。

【样例输入】

2
2
0
3
3 12 17 23

【样例输出】

3
3

【来源】

《算法竞赛进阶指南》POJ 1084