#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <bios.h>
#define RxR 15
#define Not -1
typedef int Mass[RxR][RxR];
Mass mas;/*={{-1, 0, 0, 0, 0, 0},
	  { 0,-1, 0, 0, 0, 0},
	  { 0, 0,-1, 0, 0, 0},
	  { 0, 0, 0,-1, 0, 0},
	  { 0, 0, 0, 0,-1, 0},
	  { 0, 0, 0, 0, 0,-1}};*/
typedef int Pper[RxR][3];
Pper Pnill={{0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0},
	    {0,0,0}};
struct BitF {
       int  min:1;// Флаг для первого встреченного минимума
       int  lin:1;// Флаг для поиска по линии/столбцу
       int deli:1;// Флаг для встречи удаляемой строки
       int delj:1;// Флаг для встречи удаляемого столбца
       int fixi:1;// Флаг для фиксирования левого конца маршрута
       int fixj:1;// Флаг для текущего фиксирования правого конца
       int fine:1;// Флаг для завершения поиска маршрута (будет получен на
       int   b8:1;// следующем шаге при делении)
       int   b9:1;
       int  b10:1;
       int  b11:1;
       int  b12:1;
       int  b13:1;
       int  b14:1;
       int  b15:1;
       int  b16:1;
       };
union Flag {
      unsigned int word;// Маскирует ввод всех флагов
      struct BitF bit;
      } Flags;
struct Element{
       int Num[2][RxR];// Запрещающие элементы
       Mass C;// Сам массив
       Element *up,*left,*right;// Указатели на предка и потомков
       int Psy,Leva,Levb,Step,n;// Пси, уровень-а, уровень-б, шаг, разрядность
       int Etta[3];// Перспективная пара
       Pper P,notP;// Элементы для маршрутизатора
       };
typedef Element *Ptr;// Определим тип для указателей
Ptr Head,Creeper;// Заводим 2 для главного и ползунка
int i,j,n;//рабочие
char *str,buf[5];

void MakeDiv(struct Element *Addr);

void CopyMatr(int *M_Slave,int *M_Master,int not_i,int not_j,int RStr,int RCol);

int FindMin(int *matr,int *mask,int i,int j,int not_i,int not_j);

void Reduct(struct Element *Addr);

void Perspectiv_Pair(struct Element *Addr);

struct Element* ScanTree(struct Element* Creeper,struct Element* Send_min,int* number);

int Router(struct Element* Addr);

void Dispose(struct Element* Addr);

struct Element* Method_Br_Verge(struct Element* Addr);

void draw_window(int xl,int yh,int xr,int yl,int color,int fon,int angle);

void main (void)
{
Head=(struct Element*)malloc(sizeof(struct Element));// Создаём указаталь
Head->up=Head->left=Head->right=NULL;// Все остальные обнуляем
Head->Psy=Head->Leva=Head->Levb=Head->Step=0;// Начальные значения обнуляем
Head->Etta[0]=Head->Etta[1]=Head->Etta[2]=0;// Начальные значения обнуляем
textbackground(1);
textcolor(14);
clrscr();
draw_window(1,1,80,25,15,1,0x1fbc);
gotoxy(27,2);
cout<<"Введите киличество деталей\n";
draw_window(35,5,44,7,14,4,0x4ebc);
gotoxy(4,1);
cscanf("%d",&n);
if(n<3)n=3;
if(n>15)n=15;
draw_window(1,1,80,25,15,1,0x1fbc);
gotoxy(20,1);
textcolor(14);
cout<<"Введите время переналадки линии для ";
cout<<n<<" деталей\n";
for(i=0;i<n;i++)
  for(j=0;j<n;j++){
    gotoxy(5+j*5,5+i*2);
    if(i==j){
      mas[i][j]=-1;
      cprintf("-1");
      }else
	 cscanf("%d",&(mas[i][j]));
    }

Head->n=--n;// Вносим разрядность
CopyMatr((int*)&(Head->C),(int*)&mas,Not,Not,RxR,RxR);// Копируем в С заглушку
CopyMatr((int*)&(Head->P),(int*)&Pnill,Not,Not,RxR,3);// Тоже с Р и notP
CopyMatr((int*)&(Head->notP),(int*)&Pnill,Not,Not,RxR,3);
for(j=0;j<RxR;j++)// Заносим в Num маску для запрещённых элементов
  if(j<=Head->n)Head->Num[0][j]=Head->Num[1][j]=0;
    else Head->Num[0][j]=Head->Num[1][j]=1;// Если за пределами разрядности
Creeper=Method_Br_Verge(Head);// Используем метод ветвей и границ
cprintf("\n\rСуммарное время переналадки=%5d\n\r",Creeper->Psy);
cprintf("Необходимо произвести переналадку\n\r");
for (i=0;i<=Creeper->n;i++)
 cprintf("с%5d детали на%5d деталь\n\r",(Creeper->P[i][0])+1,(Creeper->P[i][1])+1);
cprintf("решение было найдено на %5d шаге итерации\n\r",Creeper->Step);
Dispose(Head);
i=bioskey(0);
return;
}

// The function make copy from Master into Slave, cutting string i and column j
// for massiv heving size RStr x RCol
// necessary send for function real size of String and Column
void CopyMatr(int *M_Slave,int *M_Master,int not_i,int not_j,int RStr,int RCol)
{
int i,j;// Внутренние i и j
Flags.bit.deli=Flags.bit.delj=0;// Обнуляем флаги
for(i=0;i<RStr;i++){//Цикл для строк RSrt раз
  if(i!=not_i)// Если эту строку не нужно игнорировать
    for(j=0;j<RCol;j++)//Цикл для элементов столбца RCol раз
      if(j!=not_j)// Если этот столбец не нужно игнорировать
// По адресу раба пишем элемент хазяина, но если исключаемые линии массива
// уже встречались, то адрес элемента раба будет отставать от адреса хозяина
// на строку либо столбец, что и осуществляется.
      *(M_Slave+RCol*(i+Flags.bit.deli)+j+Flags.bit.delj)=*(M_Master+RCol*i+j);
//Why 5+Flags.bit.deli well be equal 4, but not 5 ?
      else Flags.bit.delj=1;// Встретился элемент столбца который исключаем
  else Flags.bit.deli=1;// Встретилась строка которую пропустим и организо-
// вываем смешение следующих строк раба на одну относительно хозяина
  Flags.bit.delj=0;// Онулируем встречу элемента столбца, т.к. переходим на
// новую строку
  }
}

// The  function searches for a mimimum in line, or in column depending on
// Flags.bit.lin, but this function can passing not_i and not_j
int FindMin(int *matr,int *mask,int i,int j,int not_i,int not_j)
{
int min=0;

Flags.bit.min=0;// Флаг означает что первый допустимый элемент ещё не встречен
if(Flags.bit.lin){ // Если ищем вдоль строки (i уже настроено по параметру)
  for (j=0;j<RxR;j++)// Цикл для элементов столбца RxR раз
    if(*(mask+RxR+j)!=1)// Смотрим разрешён ли этот столбец
      if((*(matr+RxR*i+j)>=0)&&(j!=not_j))// Смотрим ружно ли учитавать это
	if(Flags.bit.min){
	  if(min>*(matr+RxR*i+j))min=*(matr+RxR*i+j);// Если min > текущего,
// то в min заносим текущий
	  }
	else{// Если это первый допустимый элемент, то считаем
// его за минимальный
	  min=*(matr+RxR*i+j);
	  Flags.bit.min=1;// Учитываем то, что первый допустимый уже найден
	  }
    return min;// возвращаем
  }
else // Если будем искать минимум по заданному столбцу
  for (i=0;i<RxR;i++)
    if(*(mask+i)!=1)
      if((*(matr+RxR*i+j)>=0)&&(i!=not_i))
	if(Flags.bit.min){
	  if(min>*(matr+RxR*i+j))min=*(matr+RxR*i+j);
	  }
	else{
	  min=*(matr+RxR*i+j);
	  Flags.bit.min=1;
	  }
return min;
}

//This functin mekes reduction to a normal kind(view), and put down Psy=hi+hj
void Reduct(struct Element *Addr)
{
int min,hi=0,hj=0; // Приравниваем сумму минимумов по строкам и по столбцам к нулю
Flags.bit.lin=1; // Будем искать вдоль строки
for (i=0;i<RxR;i++){
  if(Addr->Num[0][i]!=1){// Перебираем разрешённые строки
// и ищем минимум в С с маской Num, в текущей строке i начиная с нуля
// элемент который не нужно учитывать отсутствует
    min=FindMin((int*)&(Addr->C),(int*)&(Addr->Num),i,0,Not,Not);
    hi+=min; // Суммируем полученный минимум в hi
    for (j=0;j<RxR;j++)
// Вычитаем из разрешённых элементов текущей строки минимальное значение
      if((Addr->C[i][j]>=0)&&(Addr->Num[1][j]!=1))Addr->C[i][j]-=min;
    }
  }
Flags.bit.lin=0; // Будем искать вдоль столбцов
for (j=0;j<RxR;j++){
  if(Addr->Num[1][j]!=1){// Перебираем разрешённые столбцы
    min=FindMin((int*)&(Addr->C),(int*)&(Addr->Num),0,j,Not,Not);
// и ищем минимум в С с маской Num, в текущем столбце j начиная с нуля
// элемент который не нужно учитывать отсутствует
    hj+=min;
    for (i=0;i<RxR;i++)
      if((Addr->C[i][j]>=0)&&(Addr->Num[0][i]!=1))Addr->C[i][j]-=min;
    }
  }
Addr->Psy=hi+hj;// Заносим в Psy значение равное сумме hi и hj
}

//This function determines a competing pair
// It's necessary to transfer (real size)-1
void Perspectiv_Pair(struct Element *Addr)
{
int i,j,rez=0;
Addr->Etta[2]=0;// сумма минимума по строке и столбцу перспективного элемента
for(i=0;i<RxR;i++)
  if(Addr->Num[0][i]!=1)// Если столбец разрешён
  for(j=0;j<RxR;j++)
    if((Addr->C[i][j]==0)&&(Addr->Num[1][j]!=1)){// Если элемент равен 0 и
// не запрещён
      rez=0;// сумма минимума по строке и столбцу перспективного элемента
      Flags.bit.lin=1;// Будем искать минимум вдоль строки
// передаём адрес первого элемента массива С и адрес перваго элемента маски
// Num, ищем по строке i (она разрешена) начиная с 0, но элемент (i,j) нужно
// пропустить
      rez=FindMin((int*)&(Addr->C),(int*)&(Addr->Num),i,0,i,j);
      Flags.bit.lin=0;
      rez+=FindMin((int*)&(Addr->C),(int*)&(Addr->Num),0,j,i,j);
      if(Addr->Etta[2]<=rez){
	Addr->Etta[0]=i;//немер строки с перспективным элементом
	Addr->Etta[1]=j;//немер столбца с перспективным элементом
	Addr->Etta[2]=rez;//значение перспективного элемента
	}
      }
}

void MakeDiv(struct Element *Addr)
{
int i,j;
Ptr Right,Left;
Right=(struct Element*)malloc(sizeof(struct Element));//Заводим структуру
if(!Right){// Проверяем есть ли ещё память
  printf("Not memory");
  exit(1);
  }
Addr->right=Right;//В правый адрес предка заносим адрес структуры
Right->up=Addr;//В полученную структуру заносим адрес предка
Right->left=Right->right=NULL;//Адрес потомков равен нулю
Right->n=Addr->n;//Разрядность потомка равна родителю
Right->Etta[0]=Right->Etta[1]=Right->Etta[2]=0;// Обнуляем мусор
CopyMatr((int*)&(Right->C),(int*)&(Addr->C),Not,Not,RxR,RxR);//Копируем С
CopyMatr((int*)&(Right->Num),(int*)&(Addr->Num),Not,Not,2,RxR);//Копируем маску
Right->C[Addr->Etta[0]][Addr->Etta[1]]=Not;//Пологаем элемент матрицы,
//соответствующий перспективному, равным бесконечности
Reduct(Right);// Приводим к нормальному виду
Right->Psy=Right->Psy+Addr->Psy;// Оценка Psy суммируется с оценкой предка
Right->Step=Addr->Step;//Записываем шаг итерации (равен шагу предка)
Right->Leva=Addr->Leva;//Нумерация уровня предка
Right->Levb=2;//Нумерация потомка
CopyMatr((int*)&(Right->P),(int*)&(Addr->P),Not,Not,RxR,3);//Копируем Р
CopyMatr((int*)&(Right->notP),(int*)&(Addr->notP),Not,Not,RxR,3);//Копируем
// и в следующую строку заносим координаты перспективной пары предка которая
// была приравнена к бесконечности
i=0;
while(Right->notP[i][0]!=Right->notP[i][1])i++;// Ищем последний элемент
Right->notP[i][0]=Addr->Etta[0];// и пишем в него
Right->notP[i][1]=Addr->Etta[1];
//***********************left branch******************
Left=(struct Element*)malloc(sizeof(struct Element));
if(!Left){
  printf("Not memory");
  exit(1);
  }
Addr->left=Left;
Left->up=Addr;
Left->left=Left->right=NULL;
Left->n=Addr->n;
Left->Etta[0]=Left->Etta[1]=Left->Etta[2]=0;
CopyMatr((int*)&(Left->C),(int*)&(Addr->C),Not,Not,RxR,RxR);
CopyMatr((int*)&(Left->Num),(int*)&(Addr->Num),Not,Not,2,RxR);
//Запрещаем строку и столбец в которых лежит перспестивный элемент предка
Left->Num[0][Addr->Etta[0]]=1;
Left->Num[1][Addr->Etta[1]]=1;
Left->C[Addr->Etta[1]][Addr->Etta[0]]=Not;//Пологаем обратный элемент равнам
//бесконечности
CopyMatr((int*)&(Left->P),(int*)&(Addr->P),Not,Not,RxR,3);
CopyMatr((int*)&(Left->notP),(int*)&(Addr->notP),Not,Not,RxR,3);
i=0;
while(Left->P[i][0]!=Left->P[i][1])i++;
Left->P[i][0]=Addr->Etta[0];
Left->P[i][1]=Addr->Etta[1];
i=Router(Left);// Запускаем маршрутищзатор
//printf("есть %5d\n",i);
//scanf("%d",i);
Reduct(Left);//Приводим к нормальному виду
Left->Psy=Left->Psy+Addr->Psy;// Оценка Psy суммируется с оценкой предка
Left->Step=Addr->Step;
Left->Leva=Left->Leva;
Left->Levb=1;
}


// This function scaning Tree of Element starting to send address and search
// necessary leaf
struct Element* ScanTree(struct Element* Creeper,struct Element* Send_min,int* number)
// Просматривает структуру по адресу ползунка и если в листе, то сравнивает
// его оценку с минимальной оценкой находящейся по адресу Send_min
// если оценка ползунка меньше посланной, то теперь будет пересылаться адрес
// ползунка, если нет, то дольше продолжит пересылаться посланный минимум
// Функция попутно меняет нумерацию листьев и наращивает значение итерации
{
//Идём налево
if(Creeper->left!=NULL)Send_min=ScanTree(Creeper->left,Send_min,number);
else{//Значит мы в листе
    Creeper->Step=Head->Step;
    Creeper->Leva=*number;
    Creeper->Levb=0;
    (*number)++;
    if(Send_min==NULL) return Creeper;//если это первый встретившийся лист
    else
      if(Send_min->Psy>Creeper->Psy) return Creeper;//если в этом листе меньше
      else return Send_min;
    }
//Теперь идём направо
if(Creeper->right!=NULL)Send_min=ScanTree(Creeper->right,Send_min,number);
else{
    Creeper->Step=Head->Step;
    Creeper->Leva=*number;
    Creeper->Levb=0;
    (*number)++;
    if(Send_min==NULL) return Creeper;
    else
      if(Send_min->Psy>Creeper->Psy) return Creeper;
      else return Send_min;
    }
return Send_min;
}

// This function search long combination of perspectiv pair
// and return maximum length of uninterrupted route
int Router(struct Element* Addr)
{
int i=0,j,fix_i=0,fix_j=0,cur_ring,max_ring=0;
do{
  Flags.bit.fixi=0;// Устанавливаем флаг в ноль
  do{// Делаем пока не встретится непомеченый и не пустой элемент
    if(Addr->P[i][0]!=Addr->P[i][1]){
      fix_i=Addr->P[i][0];//фиксируем левую точку
      fix_j=Addr->P[i][1];//фиксируем правую точку
      Flags.bit.fixi=1;//взводим флаг
      }
      else i++;//наращиваем
    }while((i<RxR)&&(!Flags.bit.fixi));// или переполнили i
//  for(j=0;j<RxR;j++)// Обращаем все метки в нули
//  Addr->P[j][2]=0;
  cur_ring=1;//равно 1 т.к. одну пару уже нашли
  for(j=0;j<RxR;j++)// Обращаем все метки в нули
  Addr->P[j][2]=0;
  do{
    Flags.bit.fixj=0;//новых фиксаций правой точки ещё нет
    for(j=0;j<RxR;j++)// делаем с верху в низ
      if((fix_j==Addr->P[j][0])&&(Addr->P[j][0]!=Addr->P[j][1])&&(Addr->P[j][2]!=1)){//есть не
	fix_j=Addr->P[j][1];//пустое продолжение, переставляем на него
	Addr->P[j][2]=1;// помечаем, что здесь уже учтено
	Flags.bit.fixj=1;// на этом шаге были новые продолжения маршрута
	cur_ring++;// увеличиваем счётчик длины
	}
    }while(Flags.bit.fixj);// если небыло ниодного нового дополнения
  if(cur_ring<Addr->n)Addr->C[fix_j][fix_i]=-1;//если это не предпоследний шаг
    else Flags.bit.fine=1;// это предпоследний, после деления конец
  max_ring=(max_ring<cur_ring)?cur_ring:max_ring;//выбираем максимальную длину
  i++;//наращиваем
  }while((i<RxR)&&(!Flags.bit.fine));//выход если превысили размер или fine
for(i=0;i<RxR;i++)// Обращаем все метки в нули
  Addr->P[i][2]=0;
return max_ring;
}


// This function cleaning memory
void Dispose(struct Element* Addr)
{
while ((Addr->left!=NULL)&&(Addr->right!=NULL)){//Пока не в листе
  if (Addr->left!=NULL) Dispose(Addr->left);//если можно, то идти влево
  if (Addr->right!=NULL) Dispose(Addr->right);//или в право
    }
if((Addr->up!=NULL)&&((Addr->up)->left!=NULL))(Addr->up)->left=NULL;
//Мы в листе, если не вершина,то затираем левый указатель родителя
if((Addr->up!=NULL)&&((Addr->up)->left==NULL))(Addr->up)->right=NULL;
//Мы в другом листе, если не вершина,то затираем правый указатель родителя
free(Addr);// Отрываем листик
}

struct Element* Method_Br_Verge(struct Element* Addr)
{
int min;
Ptr Creeper;// заводим переменную типа указатель
Reduct(Addr);// Приводим С к нормальному виду
Perspectiv_Pair(Addr);// Находим перспективную пару
MakeDiv(Addr);// Производим деление на две ветви
while(!Flags.bit.fine){
  Head->Step+=1;
  Creeper=NULL;// Обнуляем указатель на перспективное множество
  min=0;// Начальное значение пересчёта положим равным нулю
  Creeper=ScanTree(Addr,Creeper,&min);// Получаем в ползунок перспективное множество
  Perspectiv_Pair(Creeper);// Находим в этом множестве перспективную пару
  MakeDiv(Creeper);// Производим деление на два нодмножества
}
Head->Step+=1;
Creeper=NULL;// Обнуляем указатель на перспективное множество
min=0;// Начальное значение пересчёта положим равным нулю
Creeper=ScanTree(Addr,Creeper,&min);// Получаем в ползунок перспективное множество
Perspectiv_Pair(Creeper);// Находим в этом множестве перспективную пару
MakeDiv(Creeper);// Производим деление на два нодмножества
Creeper=Creeper->left;// Спускаемся в левый лист там ответ
return Creeper;// возвращаем структуру с ответом
}


void draw_window(int xl,int yh,int xr,int yl,int color,int fon,int angle)
{
int i,coord;
window(xl,yh,xr,yl);
textbackground(fon);
clrscr();
textcolor(color);
for(i=2;i<=xr-xl;i++){
  gotoxy(i,1);
  cprintf("═");
  gotoxy(i,yl-yh+1);
  cprintf("═");
  }
for(i=2;i<=yl-yh;i++){
    gotoxy(1,i);
    cprintf("║");
    gotoxy(xr-xl+1,i);
    cprintf("║");
    }
gotoxy(1,1);
cprintf("╔");
gotoxy(xr-xl+1,1);
cprintf("╗");
gotoxy(1,yl-yh+1);
cprintf("╚");
coord=160*(yl-1)+(xr-1)*2;
asm{
  mov ax,0b800h
  mov es,ax
  mov di,coord
  mov ax,angle
  mov es:[di],ax
  }
window(xl+1,yh+1,xr-1,yl-1);
}