?? 3568916_ac_0ms_448k.cc
字號:
#include <iostream>
#include <algorithm>
#define inf 100000000
using namespace std;
int n;
char chess[5][5];
int map[50][50];
int LINK[50], b[50];
int l, r;
int idl[5][5], idr[5][5];
void input()
{
for (int i = 0; i < n; i++)
{
cin >> chess[i];
}
}
bool valid(int x, int y)
{
return !(x < 0 || y < 0 || x >= n || y >= n || chess[x][y] == 'X');
}
void build()
{
l = 0;
r = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (valid(i, j))
{
l++;
while (valid(i, j))
{
idl[i][j] = l;
j++;
}
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (valid(j, i))
{
r++;
while (valid(j, i))
{
idr[j][i] = r;
j++;
}
}
}
}
memset(map, 0, sizeof(map));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (chess[i][j] == '.')
{
map[idl[i][j]][idr[i][j]] = 1;
}
}
}
}
int dfs(int v)
{
int i;
for (i = 1; i <= r; i++)
{
if (map[v][i] && !b[i])
{
b[i] = 1;
if (LINK[i] == 0 || dfs(LINK[i]))
{
LINK[i] = v;
return 1;
}
}
}
return 0;
}
void match()
{
int ans = 0;
memset(LINK, 0, sizeof(LINK));
for (int i = 1; i <= l; i++)
{
memset(b, 0, sizeof(b));
ans += dfs(i);
}
printf("%d\n", ans);
}
int main()
{
while (cin >> n && n != 0)
{
input();
build();
match();
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -