题意
N*M矩阵，有空地('o')、草地('*')、墙('#‘)，机器人能攻击到上下左右，不被墙挡住的方位。
并且机器人只能被放置在空地上。问能放置的最大数量机器人，相互间不能攻击到。
解题思路
对于所有空地，能够攻击到的相互之间冲突，即可连接成边，然后题目就转换成了 最大独立集问题。
但是本题 顶点数量为 50*50 = 2500， 果断TLE。
另外我们可以发现，通过
将每一行相互攻击到的空格位置看成一个点，这些点命名为 {A}
将每一列相互攻击到的空格位置看成一个点，这些点命名为 {B}
则图就转换了二分图， 对于 顶点集 {A} 与 {B} 而言， 之间存在共用的空格，则其相互间存在冲突，则当前点只能放一个机器人。
则通过将其连边， 那么问题就转换成了求 没有公共顶点的最大边集（最大匹配）。
#include#include #include const int N = 51;char mp[N][N];int n, m;int row,col,r[N][N],c[N][N];bool g[N*N][N*N];int ma[N*N], mb[N*N];bool vis[N*N];void init(){ memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); memset(g,0,sizeof(g)); row = col = -1; bool flag = false; for(int i = 0; i < n; i++){ flag = false; for(int j = 0; j < m; j++){ if( mp[i][j] == 'o' ){ if(!flag) ++row; r[i][j] = row, flag = true; } else if( mp[i][j] == '#' ) flag = false; } } for(int j = 0; j < m; j++){ flag = false; for(int i = 0; i < n; i++){ if( mp[i][j] == 'o' ){ if( !flag ) ++col; c[i][j] = col, flag = true; } else if( mp[i][j] == '#' ) flag = false; } } col++; row++; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if( mp[i][j] == 'o' ) g[ r[i][j] ][ c[i][j] ] = 1;}int path( int u ){ for(int v = 0; v < col; v++){ if( g[u][v] && !vis[v] ){ vis[v] = 1; if( ma[v] == -1 || path( ma[v] ) ){ ma[v] = u; mb[u] = v; return 1; } } } return 0;}void MaxMatch(){ memset( ma,0xff,sizeof(ma)); memset( mb,0xff,sizeof(mb)); int res = 0; for(int i = 0; i < row; i++){ if( mb[i] == -1 ){ memset( vis, 0, col*sizeof(int)); res += path( i ); } } printf("%d\n", res );}int main(){ int T; scanf("%d", &T); for(int Case = 1; Case <= T; Case++){ scanf("%d%d", &n,&m); for(int i = 0; i < n; i++) scanf("%s",mp[i]); printf("Case :%d\n", Case); init(); MaxMatch(); } return 0;}