?? pku2226.cpp
字號:
#include <stdio.h>
#include <string.h>
#define size 50
#define psize 500
int path[psize][psize];
int vis[psize];
int match[psize];
char map[size][size];
int id1[size][size];
int id2[size][size];
int m, n, M, N;
int cnt;
int DFS(int p)
{
int i, t;
for (i = 0; i < N; i++)
{
if (!vis[i] && path[p][i])
{
vis[i] = 1;
t = match[i];
match[i] = p;
if (t == -1 || DFS(t))
{
return 1;
}
match[i] = t;
}
}
return 0;
}
void Solve()
{
int i, j, cnt;
for (i = 0; i < m; i++)
{
scanf("%s", map[i]);
}
memset(id1, -1, sizeof(id1));
memset(id2, -1, sizeof(id2));
M = 0;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (map[i][j] == '*')
{
if (j == 0 || map[i][j - 1] != '*')
id1[i][j] = M++;
else
id1[i][j] = id1[i][j - 1];
}
}
}
N = 0;
for (j = 0; j < n; j++)
{
for (i = 0; i < m; i++)
{
if (map[i][j] == '*')
{
if (i == 0 || map[i - 1][j] != '*')
id2[i][j] = N++;
else
id2[i][j] = N - 1;
}
}
}
memset(path, 0, sizeof(path));
memset(match, -1, sizeof(match));
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (map[i][j] == '*')
path[id1[i][j]][id2[i][j]] = 1;
}
}
for (i = 0, cnt = 0; i < M; i++)
{
memset(vis, 0, sizeof(vis));
cnt += DFS(i);
}
printf("%d\n", cnt);
}
int main()
{
while (EOF != scanf("%d %d", &m, &n))
{
Solve();
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -