题意：给你一个正方形棋盘。每个棋子可以直线攻击，除非隔着石头。现在要求所有棋子都不互相攻击，问最多可以放多少个棋子。
这个题可以用搜索来做。每个棋子考虑放与不放两种情况，然后再判断是否能互相攻击来剪枝。最后取可以放置的最大值。
这里我转化成求最大独立集来做。
首先将每个空地编号，对于每个空地，与该位置可以攻击到的空地连边。找最多的空地使得不互相攻击，即求该图的最大独立集。与搜索做法基本一致，但是说法略有不同。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
][];
][];
][];
int n,cn,ans;
];
void init()
{
memset(gl,,sizeof(gl));
cn=;
; i<n; ++i)
; j<n; ++j)
if(grid[i][j]=='.')
g[i][j]=++cn;
;
; i<n; ++i)
; j<n; ++j)
if(grid[i][j]=='.')
{
int &now=g[i][j];
; k<n&&g[i][k]; ++k)
gl[now][g[i][k]]=true;
; k>=&&g[i][k]; --k)
gl[now][g[i][k]]=true;
; k<n&&g[k][j]; ++k)
gl[now][g[k][j]]=true;
; k>=&&g[k][j]; --k)
gl[now][g[k][j]]=true;
}
ans=;
memset(col,,sizeof(col));
}
void dfs(int d,int res)
{
if(d>cn) ans=max(ans,res);
else
{
bool ok=true;
; i<=cn; ++i)
if(gl[d][i]&&col[i]) ok=false;
if(ok)
{
col[d]=true;
dfs(d+,res+);
col[d]=false;
}
dfs(d+,res);
}
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
; i<n; ++i)
scanf("%s",grid[i]);
init();
dfs(,);
printf("%d\n",ans);
}
;
}