using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TSA_munkasok_beadando
{
    class Program
    {
        static void feltolt_munkasok(int N, ref int[,] m)
        {
            Random rn = new Random();
            
            int i = 0;
            bool van1 = false;
            while(i < N)
            {
                for (int j = 0; j < N; j++)
                {
                    m[i, j] = rn.Next(0, 2);
                   if (m[i, j] == 1)
                        van1 = true;
                }
                if (van1)
                {
                    i++;
                    van1 = false;
                }
            }
            Console.WriteLine("A munkások mátrixa: (A sorban a munkások, oszlopokban pedig az általuk elvállalható munka van rögzítve.)");
            Console.Write("  ");
            for (i = 0; i < N; i++)
            {
                Console.Write(" {0}", i+1);
            }
            Console.WriteLine();

            for ( i = 0; i < N; i++)
            {
                Console.Write(" {0}", i+1);
                for (int j = 0; j < N; j++)
                {
                    Console.Write(" {0}", m[i,j]);

                }
                Console.WriteLine();
            }

        }

        static void munkakiosztas(int[,] m, ref List<int> munkas, ref List<int> munka, int N, int i, int j)
        {

            while (i < N)
            {

                while (j < N && munkas.IndexOf(i) == -1)
                {

                    if (m[i, j] == 1 && munka.IndexOf(j) == -1)
                    {

                        munka.Add(j);
                        munkas.Add(i);

                    }
                    j++;
                }
                if (munkas.IndexOf(i) == -1)
                    if (i == 0)
                        i = N;
                    else
                    {
                        int x = munka.Last();
                        munka.Remove(munka.Last());
                        munkas.Remove(munkas.Last());
                        munkakiosztas(m, ref munkas, ref munka, N, i - 1, x + 1);
                    }
                i++;
                j = 0;
            }
        }

        static void Main(string[] args)
        {
            int N = 5; //ennyi munkás van

            int[,] munkasok = new int[N, N]; 
            List<int> munkas = new List<int>(); //munkások listája
            List<int> munka = new List<int>(); //elvállalt munka

            feltolt_munkasok(N, ref munkasok);

            munkakiosztas(munkasok, ref munkas, ref munka, N, 0, 0);

            if (munkas.Count() < N)

                Console.WriteLine("Nincs lehetséges munkakiosztás!");
            else
                Console.WriteLine("Egy lehetséges munkakiosztás:");
                for (int i = 0; i < munkas.Count(); i++)
                {
                    
                    Console.WriteLine("{0}. munkás - {1}. munka", munkas[i]+1, munka[i]+1);
                }



            Console.ReadKey();
        }
    }
}

    
