Pagini recente » Cod sursa (job #2862596) | Cod sursa (job #2890860) | Cod sursa (job #2889665) | Cod sursa (job #2476909) | Cod sursa (job #2639817)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 26;
vector <int> G[NMAX + 5];
int l[NMAX + 5] , r[NMAX + 5] , row[NMAX + 5] , col[NMAX + 5] , viz[NMAX + 5];
char sol[NMAX + 5];
int path(int u)
{
int v , i;
if(viz[u])
return 0;
viz[u] = 1;
for(i = 0 ; i < G[u].size() ; i ++)
{
v = G[u][i];
if(!r[v])
{
l[u] = v;
r[v] = u;
return 1;
}
}
for(i = 0 ; i < G[u].size() ; i ++)
{
v = G[u][i];
if(path(r[v]))
{
l[u] = v;
r[v] = u;
return 1;
}
}
return 0;
}
void dfs(int u)
{
int v , i;
viz[u] = 1;
row[u] = 0;
for(i = 0 ; i < G[u].size() ; i ++)
{
v = G[u][i];
if(!viz[r[v]])
{
col[v] = 1;
dfs(r[v]);
}
}
}
int main()
{
freopen("paznici.in" , "r" , stdin);
freopen("paznici.out" , "w" , stdout);
int n , m , x , cuplaj , i , j , gasit;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++)
for(j = 1 ; j <= m ; j ++)
{
scanf("%1d" , &x);
if(x)
G[i].push_back(j);
}
cuplaj = 0;
do
{
memset(viz , 0 , sizeof(viz));
gasit = 0;
for(i = 1 ; i <= n ; i ++)
if(!l[i] && path(i))
{
cuplaj ++;
gasit = 1;
}
}
while(gasit);
memset(viz , 0 , sizeof(viz));
for(i = 1 ; i <= n ; i ++)
if(l[i])
row[i] = 1;
for(i = 1 ; i <= n ; i ++)
if(!l[i])
dfs(i);
for(i = 1 ; i <= n ; i ++)
if(row[i])
printf("%c" , i + 'A' - 1);
for(i = 1 ; i <= m ; i ++)
if(col[i])
printf("%c" , i + 'a' - 1);
return 0;
}