#include <iostream>
using namespace std;
int findPos(int* a,int val,int n){
cout << " ";
for(int i=0;i<n;i++)
if(a[i]==val) return i;
return -1;
}
void print(int* a, int n){
for (int i = 0; i < n ; i++) cout << a[i] << " " ;
cout << endl;
}
void parkinglot(int* a, int *b, int n){
cout << "Init: " ;
print(a,n);
int count = 0;
int currIdx = 0;
for (int i = 0; i < n; i++) {
if (a[i] != 0 && b[i] != a[i]) {
int zIdx = findPos(a, 0, n);
swap(a[i], a[zIdx]);
count++;
print(a,n);
if(b[i]!=0){
currIdx = findPos(a, b[i], n);
swap(a[i], a[currIdx]);
print(a,n);
count++;
}
}
else if(a[i]==0 && b[i] != a[i]){
currIdx = findPos(a, b[i], n);
swap(a[i], a[currIdx]);
print(a,n);
count++;
}
}
cout << "Finl: " ;
print(a,n);
cout << "Min swaps: " << count << endl;
}
int main()
{
int src[] = {1,2,3,0,4};
int tgt[] = {0,3,2,1,4};
cout << "Rearrange parking lot in Min swaps!" << endl;
int n = sizeof(src)/sizeof(src[0]);
parkinglot(src,tgt,n);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBmaW5kUG9zKGludCogYSxpbnQgdmFsLGludCBuKXsKICAgIGNvdXQgPDwgIiAgICAgICI7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgIGlmKGFbaV09PXZhbCkgcmV0dXJuIGk7CiAgICByZXR1cm4gLTE7Cn0KCnZvaWQgcHJpbnQoaW50KiBhLCBpbnQgbil7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG4gOyBpKyspIGNvdXQgPDwgYVtpXSA8PCAgIiAiIDsKICAgIGNvdXQgPDwgZW5kbDsKfQoKdm9pZCBwYXJraW5nbG90KGludCogYSwgaW50ICpiLCBpbnQgbil7CgoJCWNvdXQgPDwgIkluaXQ6ICIgOwoJCXByaW50KGEsbik7CgoJCWludCBjb3VudCA9IDA7CgkJaW50IGN1cnJJZHggPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJCWlmIChhW2ldICE9IDAgJiYgYltpXSAhPSBhW2ldKSB7CgkJCQlpbnQgeklkeCA9IGZpbmRQb3MoYSwgMCwgbik7CiAgICAgICAgICAgICAgICBzd2FwKGFbaV0sIGFbeklkeF0pOwogICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgIHByaW50KGEsbik7CiAgICAgICAgICAgICAgICBpZihiW2ldIT0wKXsKICAgICAgICAgICAgICAgICAgICBjdXJySWR4ID0gZmluZFBvcyhhLCBiW2ldLCBuKTsKICAgICAgICAgICAgICAgICAgICBzd2FwKGFbaV0sIGFbY3VycklkeF0pOwogICAgICAgICAgICAgICAgICAgIHByaW50KGEsbik7CiAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgIH0KCQkJfQoKCQkJZWxzZSBpZihhW2ldPT0wICYmIGJbaV0gIT0gYVtpXSl7CiAgICAgICAgICAgICAgICBjdXJySWR4ID0gZmluZFBvcyhhLCBiW2ldLCBuKTsKICAgICAgICAgICAgICAgIHN3YXAoYVtpXSwgYVtjdXJySWR4XSk7CiAgICAgICAgICAgICAgICBwcmludChhLG4pOwogICAgICAgICAgICAgICAgY291bnQrKzsKCQkJfQoJCX0KCgkJY291dCA8PCAiRmlubDogIiA7CiAgICAgICAgcHJpbnQoYSxuKTsKCQljb3V0IDw8ICJNaW4gc3dhcHM6ICIgPDwgY291bnQgPDwgZW5kbDsKCn0KCmludCBtYWluKCkKewogICAgaW50IHNyY1tdID0gezEsMiwzLDAsNH07CiAgICBpbnQgdGd0W10gPSB7MCwzLDIsMSw0fTsKICAgIGNvdXQgPDwgIlJlYXJyYW5nZSBwYXJraW5nIGxvdCBpbiBNaW4gc3dhcHMhIiA8PCBlbmRsOwogICAgaW50IG4gPSBzaXplb2Yoc3JjKS9zaXplb2Yoc3JjWzBdKTsKICAgIHBhcmtpbmdsb3Qoc3JjLHRndCxuKTsKICAgIHJldHVybiAwOwp9Cg==