Bildiğiniz gibi dünya üzerindeki siyasi haritalar, sadece 4 renk kullanılarak boyanabilmektedir. Hadi bu işlemi Türkiye haritasında deneyelim.
Kodu çalıştırmak için, öncelikle elimizde aşağıdaki değişkenlerin olduğunu varsayıyorum.
// i. şehir j. şehre komşu mu?
bool komsu[SEHIR_SAYISI][SEHIR_SAYISI] = {true veya false}
// boyamada kullanılacak renkler
char renkler[5] = {SARI, TURUNCU, KIRMIZI, YEŞİL, MAVİ}
// şehirlerin boyanma sırası
vector<int> sira; // {3,24,12,...} gibi atanacaklar
// boyama işleminin bitmesine kolay karar verebilmek için bir sayaç
int siradaki = 0; // 0 --> SEHIR_SAYISI
Bu durumda aşağıdaki özyinelemeli olarak çalışan fonksiyon yardımıyla boyama sırasını ve şehirlerin renklerini belirleyebiliriz:
bool Boya(int k = 0)
{
bool bos[] = {true, true, true, true, true}; // kullanabileceğim renkler
int ekleme = 0;
for(int i=0; i<SEHIR_SAYISI; ++i)
if(komsu[k] && renkler > 0)
bos[renkler-1] = false;
else if(komsu[k] && renkler == 0)
{
renkler = -1;
sira.push_back(i);
++ekleme;
}
for(int i=0; i<5; ++i)
if(bos)
{
if(i == 4) // anneye dön
{
for(int j=0; j<ekleme; ++j)
{
renkler[sira[sira.size()-1]] = 0;
sira.pop_back();
}
--siradaki;
return false;
}
renkler[k] = i+1;
if(siradaki == SEHIR_SAYISI-1)
return true;
if(Boya(sira[++siradaki]))
break;
}
return true;
}
Kodu çalıştırmak için, öncelikle elimizde aşağıdaki değişkenlerin olduğunu varsayıyorum.
// i. şehir j. şehre komşu mu?
bool komsu[SEHIR_SAYISI][SEHIR_SAYISI] = {true veya false}
// boyamada kullanılacak renkler
char renkler[5] = {SARI, TURUNCU, KIRMIZI, YEŞİL, MAVİ}
// şehirlerin boyanma sırası
vector<int> sira; // {3,24,12,...} gibi atanacaklar
// boyama işleminin bitmesine kolay karar verebilmek için bir sayaç
int siradaki = 0; // 0 --> SEHIR_SAYISI
Bu durumda aşağıdaki özyinelemeli olarak çalışan fonksiyon yardımıyla boyama sırasını ve şehirlerin renklerini belirleyebiliriz:
bool Boya(int k = 0)
{
bool bos[] = {true, true, true, true, true}; // kullanabileceğim renkler
int ekleme = 0;
for(int i=0; i<SEHIR_SAYISI; ++i)
if(komsu[k] && renkler > 0)
bos[renkler-1] = false;
else if(komsu[k] && renkler == 0)
{
renkler = -1;
sira.push_back(i);
++ekleme;
}
for(int i=0; i<5; ++i)
if(bos)
{
if(i == 4) // anneye dön
{
for(int j=0; j<ekleme; ++j)
{
renkler[sira[sira.size()-1]] = 0;
sira.pop_back();
}
--siradaki;
return false;
}
renkler[k] = i+1;
if(siradaki == SEHIR_SAYISI-1)
return true;
if(Boya(sira[++siradaki]))
break;
}
return true;
}