Cod sursa(job #3368199)

Utilizator Daniel150212daniel munteanu Daniel150212 Data 13 octombrie 2026 15:08:42
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
using namespace std;
int v[125][125];
int n, m;
int main()
{
  cin>>m>>n;
  for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
      cin>>v[i][j];
    }
  }
  int minim=150000, a, b;
  for(int culoare=1; culoare<=n; culoare++){
    for(int coloana=1; coloana<=n; coloana++){
      vector<bool> liberrand(m+1, false);
      int sum=0;
      for(int s=1; s<=m; s++){
        if(v[s][coloana]!=culoare){
          liberrand[s]=true;
        }
      }
      for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
          if(j==coloana) continue;
          if(v[i][j]==culoare){
            if(liberrand[i]){
              liberrand[i]=false;
              sum+=abs(j-coloana);
            }
            else {
              int minn=150, poz=0;
              for(int k=1; k<=m; k++){
                if(liberrand[k] && abs(k-i)<minn){
                  minn=abs(k-i);
                  poz=k;
                }
              }
              liberrand[poz]=false;
              sum+=abs(j-coloana)+abs(poz-i);
            }
          }
        }
      }
      if(sum<minim) {
        a=culoare;
        b=coloana;
        minim=sum;
      }
    }
  }
  cout<<minim<<" "<<a<<" "<<b;
}