本文主要是介绍ZOJ1654，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:给一个地图，分空地o 草地* 和墙壁#，可以在空地上放 向上下左右四个方向放激光【激光能穿过草无法穿墙】的机器人，问最多能放多少这样的机器人
题解：原理跟poj上那个 ”在一个点上放了以后该行该列都没发放“的原理是一样的
poj那道题是 每一行，每一列都算一块，然后X行和Y列的 交点【放置机器人的位置】就是 x-y 这条边
而这题有墙，所以 把每行和列都按照墙的分割，然后将 分块后的行列 连边【当他们的交点为空地时】
最后求一下最大匹配
#include<bits/stdc++.h>using namespace std;
const int MAXN = 2505;
#define _clr(x) memset(x, 0xff, sizeof(int) * MAXN)
int mk[MAXN], match1[MAXN], match2[MAXN], mat[MAXN][MAXN], n, m;
int path(int i){for (int j = 0; j < m; j++)if (mat[i][j] && !(mk[j]++) && (match2[j] < 0 || path(match2[j]))){match1[i] = j;match2[j] = i;return 1;}return 0;
}
int hungary(){int res(0);_clr(match1);_clr(match2);for (int i = 0; i < n; i++)if (match1[i] < 0){memset(mk, 0, sizeof(mk));res += path(i);}return res;
}
int nn,mm;
char s[100][100];
int xx[100][100],yy[100][100];
void Gao()
{memset(mat,0,sizeof(mat));memset(xx,0,sizeof(xx));memset(yy,0,sizeof(yy));cin>>nn>>mm;for (int i=0;i<nn;i++)scanf("%s",s[i]);int numx=0,numy=0;for (int i=0;i<nn;i++){bool line=false;for (int j=0;j<mm;j++){if (s[i][j]!='#'){if (!line)numx++;line=true;xx[i][j]=numx;}if (s[i][j]=='#')line=false;}}for (int j=0;j<mm;j++){bool line=false;for (int i=0;i<nn;i++){if (s[i][j]!='#'){if (!line)numy++;line=true;yy[i][j]=numy;}if (s[i][j]=='#')line=false;}}if (numx==0||numy==0){cout<<0<<endl;return;}for (int i=0;i<nn;i++)for (int j=0;j<mm;j++){if (s[i][j]=='o'){assert(xx[i][j]>=1);assert(yy[i][j]>=1);mat[xx[i][j]-1][yy[i][j]-1]=1;}}assert(numx<=MAXN);assert(numy<=MAXN);n=numx;m=numy;cout<<hungary()<<endl;
}
int main()
{int T,cas=1;cin>>T;while (T--){printf("Case :%d\n",cas++);Gao();}return 0;
}这篇关于ZOJ1654的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
