题意：给你一个正方形棋盘。每个棋子可以直线攻击，除非隔着石头。现在要求所有棋子都不互相攻击，问最多可以放多少个棋子。
这个题可以用搜索来做。每个棋子考虑放与不放两种情况，然后再判断是否能互相攻击来剪枝。最后取可以放置的最大值。
这里我转化成求最大独立集来做。
首先将每个空地编号，对于每个空地，与该位置可以攻击到的空地连边。找最多的空地使得不互相攻击，即求该图的最大独立集。与搜索做法基本一致，但是说法略有不同。
view code
题意：给你一个正方形棋盘。每个棋子可以直线攻击，除非隔着石头。现在要求所有棋子都不互相攻击，问最多可以放多少个棋子。
这个题可以用搜索来做。每个棋子考虑放与不放两种情况，然后再判断是否能互相攻击来剪枝。最后取可以放置的最大值。
这里我转化成求最大独立集来做。
首先将每个空地编号，对于每个空地，与该位置可以攻击到的空地连边。找最多的空地使得不互相攻击，即求该图的最大独立集。与搜索做法基本一致，但是说法略有不同。
view code