[二分图]JZOJ4612游戏

#include
#include
#include
#include
using namespace std;
const int N&＃61;60;
struct Graph {int v,nx;
}g[2*N*N*N];
int cnt,list[N*N];
int n,m;
char c[N][N];
int h[N][N],l[N][N],hcnt,ans;
int connect[N*N];
bool b,vis[N*N];void Add(int u,int v) {g[&＃43;&＃43;cnt]&＃61;(Graph){v,list[u]};list[u]&＃61;cnt;
}bool DFS(int u) {if (vis[u]) return 0;vis[u]&＃61;1;for (int i&＃61;list[u];i;i&＃61;g[i].nx)if (!connect[g[i].v]||DFS(connect[g[i].v])) {connect[g[i].v]&＃61;u;return 1;}return 0;
}int main() {scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%s",c[i]&＃43;1);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) {if (!b) cnt&＃43;&＃43;;for (int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)if (c[i][j]&＃61;&＃61;&＃39;*&＃39;) h[i][j]&＃61;cnt,b&＃61;0;else if (!b&&c[i][j]&＃61;&＃61;&＃39;#&＃39;) cnt&＃43;&＃43;,b&＃61;1;}b&＃61;0;for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;) {if (!b) cnt&＃43;&＃43;;for (int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)if (c[j][i]&＃61;&＃61;&＃39;*&＃39;) l[j][i]&＃61;cnt,b&＃61;0;else if (!b&&c[j][i]&＃61;&＃61;&＃39;#&＃39;) cnt&＃43;&＃43;,b&＃61;1;}hcnt&＃61;cnt;cnt&＃61;0;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for (int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)if (h[i][j]&&l[i][j]) Add(h[i][j],l[i][j]);for (int i&＃61;1;i<&＃61;hcnt;i&＃43;&＃43;) {memset(vis,0,sizeof vis);if (DFS(i)) ans&＃43;&＃43;;}printf("%d",ans);
}