Cod sursa(job #2639817)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 3 august 2020 23:40:02
Problema Felinare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#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;
}