Forum: D Programlama Dili RSS
Bağlantili Elemanlari Bulma
kerdemdemir #1
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Bağlantili Elemanlari Bulma
Bu görüntü işlemede çok kullanılan bir fonksiyon. Ayrıca mülakat sorularının vazgeçilmezi.

Diyelimki aşağıdaki gibi bir örneğimiz var;

      x x x x x x
      x x x x x x
      x x * * x x
      x x * * x x
      x x x * * x
      * x x x x x

 Burda bağlantılı '*' karekterlerini bulmak istiyoruz. Bu örnekte iki tane '*' grubu var birisi 6 tane '*' dan oluşmakta.
Diğeride sol alt köşede bir tane '*' dan oluşmakta.

Bunu çözebilmek için genelde DFS(depth first seach) kullanılır. Ve şöyle çirkin bir görüntü ortaya çıkar :
 
 
foo( int satir, int sutun)
{
    if ( ikiboyutluDizi[satir - 1][sutun] == '*') 
       foo(satir - 1, sutun); 
    else if ( ikiboyutluDizi[satir + 1][sutun] == '*')
       foo(satir + 1, sutun);
    else if ( ikiboyutluDizi[satir - 1 ][sutun - 1] == '*')
       foo(satir - 1, sutun - 1);  
 
//..... Böle 5 tane daha yazmam lazım if  
}


Acaba burda 8 tane if yazmak yerine iota ve enumarete ile filan bir süperlik yapabilirmiyim ?


Sevgiler
Erdem
kerdemdemir #2
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Tam kod aşağıda görülebilir. Nedense tam çalışmadı, bu msvc uzantısı olan monoD ile de debug edemedim. Ordan buraya sıplıyor debugger hiç bir şey anlamadım.DFS fonksiyonunda sadece sütün sayısı kadar for loop dönüyor. Dışardaki loop dönmüyor. 

Tam soru şu idi : http://codeforces.com/contest/828/problem/B

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.array;
import std.range;
import std.math;

int toplamSatir;
int toplamSutun;
dchar[][] kagitElemanlari;

struct BaglantiliElemanlar
{
    this(  dchar[][] ikiboyutluVeriYapisi )
    {
        m_veriYapisi = ikiboyutluVeriYapisi;
        DFS(0, 0);
    }

    void DFS ( int satir, int sutun )
    {
        if( satir < 0 || sutun < 0  )
            return;

        for ( ; satir <  m_veriYapisi.length ; satir++  ) // Bu for loop dönmüyor. sanki
        {
            for ( ; sutun <  m_veriYapisi[satir].length; sutun++  )
            {
                Isle( satir, sutun, m_veriYapisi.length, m_veriYapisi[satir].length );
            }
        }
    }

    void Isle( int satir, int sutun, ulong maxSatir, ulong maxSutun )
    {
        writeln( satir, sutun, maxSatir, maxSutun);
        if( satir < 0 || sutun < 0 || satir >= maxSatir || sutun >= maxSutun  )
            return;

        if (  m_veriYapisi[satir][sutun] == 'B' )
        {
            m_veriYapisi[satir][sutun] = 'W';
            m_geciciSonuc.Isle(satir, sutun );
            Isle(satir-1,sutun-1, maxSatir, maxSutun);                 
            Isle(satir,sutun-1, maxSatir, maxSutun);
            Isle(satir+1,sutun-1, maxSatir, maxSutun);               
            Isle(satir-1,sutun, maxSatir, maxSutun);               
            Isle(satir+1,sutun, maxSatir, maxSutun);               
            Isle(satir-1,sutun+1, maxSatir, maxSutun);           
            Isle(satir,sutun+1, maxSatir, maxSutun);       
            Isle(satir-1,sutun+1, maxSatir, maxSutun);
        }
        else
        {
            if ( m_geciciSonuc.DolulukSayisi )
                m_sonuclar ~= m_geciciSonuc;
            m_geciciSonuc.Resetle();
        }   
    }

    SiyahKareAdayi   m_geciciSonuc;
    SiyahKareAdayi[] m_sonuclar;
    dchar[][] m_veriYapisi;
}

struct SiyahKareAdayi
{
    int MaxY;
    int MinY;
    int MaxX;
    int MinX;
    int DolulukSayisi;

    this( int dolulukSayisi )
    {
        DolulukSayisi = dolulukSayisi;
    }
   
    void Resetle()
    {
        this = SiyahKareAdayi();
    }


    void Isle( int satir, int sutun )
    {
        DolulukSayisi++;
        MaxY = max( sutun, MaxY);
        MinY = min( sutun, MinY);
        MaxX = max( satir, MaxX);
        MinX = min( satir, MinX);
    }

    int BoslariBul()
    {
        int kareKenarUzunlugu = max(MaxX-MinX, MaxY-MinY);
        int kareAlani = kareKenarUzunlugu*kareKenarUzunlugu;
        return kareAlani - DolulukSayisi;
    }
   
    bool KareOlusturalabilirmi( int xMax, int yMax )
    {
        int xUzunlugu = MaxX-MinX;
        int yUzunlugu = MaxY-MinY;
        if ( xUzunlugu > yUzunlugu )
        {
            return yMax >= xUzunlugu;
        }
        else
        {
            return xMax >= yUzunlugu;
        }
    }
}


void main()
{
    auto kagitBoyutlari = stdin.readln.strip.split().map!(a => to!int(a)).array();
    toplamSatir = kagitBoyutlari[0];
    toplamSutun = kagitBoyutlari[1];
    kagitElemanlari = stdin
        .byLine()
        .take(toplamSatir)
        .map!(line => line
              .map!(a => to!dchar(a))
              .array())
        .array;

    writeln(kagitElemanlari);
    BaglantiliElemanlar baglantiliElemCozucu = BaglantiliElemanlar(kagitElemanlari);
    bool kareOlusturmaSorunlumu = baglantiliElemCozucu.m_sonuclar.any!(a => a.KareOlusturalabilirmi(toplamSatir, toplamSutun) == false );
    if ( kareOlusturmaSorunlumu )
        writeln(-1);
   
    int sonuc;
    baglantiliElemCozucu.m_sonuclar.each!( a => sonuc += a.BoslariBul() );
    writeln( sonuc );
}
acehreli (Moderatör) #3
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Ben buna ayrıntılı bakamadım ama İngilizce forumdaki konuyu gördüm:

  http://forum.dlang.org/thread/sphxvimypczbdvmumqcr@forum.d…

Debugger'ın atlaması -O (optimized) derlediğin için olabilir.

Ali
kerdemdemir #4
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Abi su debugger isini acilen cozmem lazim. Aslinda windows kullanmamin nedeni monoD'nin iyi calisiyor olmasi idi. Ama o da canimi sikti biraz. Bir bakiyim nerdeymis su -O opsiyonu.
acehreli (Moderatör) #5
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Eğer varsa, -O projeyi release olarak oluşturduğunda otomatik olarak ekleniyor olabilir.

Ali
kerdemdemir #6
Üye Eyl 2013 tarihinden beri · 123 mesaj · Konum: Danimarka
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bu cevap yazan Ivan aşmış bir arkadaş codeforce puanı muazzam. Daha da iyisi Timon kullanıcısının cevabı bu aşmış kişiden daha iyi. Timon iki iota bir cartesian product ile 8 tane fonksiyon çağrısı olayını çözdü valla. D komünitesinde gerçekten yetenekli insanlar var.
acehreli (Moderatör) #7
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
kerdemdemir:
Timon

Evet, müthiş birisi! :) Timon'un DConf sırasında iki günde yazıverdiği 'static foreach' dile eklenmek üzere. (Şu anda github master'da.)

D komünitesinde gerçekten yetenekli insanlar var.

Evet (ama başka komünitelerde de öyle). DConf'lara gidebilmenin en büyük yararı bu kişilerle sohbet etmek, yemek yemek, vs.

Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-17, 16:54:01 (UTC -08:00)