Alıntı (Salih Dinçer):
> Ben 5.'nin en üstte olduğunu biliyorum ama 3.'ü de en üstte aslında...:)
Biliyorum. Bu algoritma verilen bir noktadan yola çıkıyor. O noktada en üstteki dörtgenin numarasına bakıyor. Sonra, o dörtgeni oluşturan bütün konumlardaki en üstteki nokta yine bu dörtgene aitse, dörtgen serbest (en üstte) demektir.
Şu programda uyguladım:
import std.stdio;
import std.array;
import std.string;
import std.conv;
struct Nokta
{
size_t satır;
size_t sütun;
}
struct Dörtgen
{
Nokta solÜstKöşe;
Nokta sağAltKöşe;
int opApply(int delegate(Nokta nokta) işlem) const
{
int sonuç = 0;
foreach (satır; solÜstKöşe.satır .. sağAltKöşe.satır + 1) {
foreach (sütun; solÜstKöşe.sütun .. sağAltKöşe.sütun + 1) {
sonuç = işlem(Nokta(satır, sütun));
if (sonuç) {
return sonuç;
}
}
}
return sonuç;
}
}
struct Kağıt
{
alias size_t[] Konum; // Her konum bir dörtgen numarası dilimi
alias Konum[] Satır; // Her satır Konum diliminden oluşuyor
alias Satır[] Satırlar; // Bütün düzlem
Satırlar konumlar; // Üç boyut: satır, sütun, ve dörtgen numaraları
Dörtgen[size_t] dörtgenler; // Numaradan dörtgene eşleme tablosu
this (size_t boy, size_t en)
{
konumlar = new Satırlar(boy, en);
}
void yerleştir(Dörtgen dörtgen, size_t numara)
{
// Her konumun en üstüne bu dörtgenin parçası gelir
foreach (nokta; dörtgen) {
konumlar[nokta.satır][nokta.sütun] ~= numara;
}
// Daha sonra numarasından dörtgen elde edebilmek için
dörtgenler[numara] = dörtgen;
}
// Dörtgeni oluşturan konumların en üstünde 'numara' varsa true döndürür
bool serbest_mi(Dörtgen dörtgen, size_t numara) const
{
foreach (nokta; dörtgen) {
if (konumlar[nokta.satır][nokta.sütun].back != numara) {
// Bu dörtgenin en üstte olmadığı bir konum bulduk
return false;
}
}
// Buraya geldiysek dörtgeni oluşturan bütün noktalarda en üstte
// 'numara' var demektir. Yani dörtgen serbest.
return true;
}
void kaldır(Nokta nokta)
{
Konum konum = konumlar[nokta.satır][nokta.sütun];
if (konum.empty) {
writefln("%s konumunda dörtgen yok", nokta);
} else {
auto dörtgenNumarası = konum.back; // En üstteki dörtgenin numarası
auto dörtgen = dörtgenNumarası in dörtgenler;
// Daha önce yerleştirdiğimize göre eşleme tablosunda bulunmalı.
assert(dörtgen, format("%s numaralı dörtgen bulunamadı"));
if (serbest_mi(*dörtgen, dörtgenNumarası)) {
sil_(*dörtgen, dörtgenNumarası);
writefln("%s numaralı dörtgen silindi", dörtgenNumarası);
} else {
writefln("%s numaralı dörtgen serbest değil", dörtgenNumarası);
}
}
}
// Bu işlev arayüzün parçası değil; yalnızca bu yapı çağırsın diye...
private void sil_(Dörtgen dörtgen, size_t dörtgenNumarası)
{
foreach (nokta; dörtgen) {
konumlar[nokta.satır][nokta.sütun].popBack();
}
dörtgenler.remove(dörtgenNumarası);
}
void çiz() const
{
foreach (satır; konumlar) {
foreach (konum; satır) {
// Her konumda en üstte olanı çizeceğiz
auto görünüm = !konum.empty ? konum.back.to!string : ".";
writef(" %s", görünüm);
}
writeln();
}
}
}
void doldur(ref Kağıt kağıt)
{
kağıt.yerleştir(Dörtgen(Nokta(3, 3), Nokta(7, 7)), 1);
kağıt.yerleştir(Dörtgen(Nokta(8, 15), Nokta(10, 18)), 2);
kağıt.yerleştir(Dörtgen(Nokta(5, 5), Nokta(9, 10)), 3);
kağıt.yerleştir(Dörtgen(Nokta(4, 4), Nokta(6, 6)), 4);
}
void main()
{
auto kağıt = Kağıt(20, 20);
doldur(kağıt);
kağıt.çiz();
kağıt.kaldır(Nokta(0, 0)); // Boş bir nokta
kağıt.kaldır(Nokta(8, 8)); // Kaldırılamaz çünkü serbest değil
kağıt.kaldır(Nokta(4, 4)); // Serbest
kağıt.kaldır(Nokta(8, 8)); // Şimdi kaldırılabilir çünkü artık serbest
kağıt.çiz();
}
Program iki kere çiz() diyor. Çıktısı şöyle:
'
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . 1 4 4 4 1 . . . . . . . . . . . .
. . . 1 4 4 4 3 3 3 3 . . . . . . . . .
. . . 1 4 4 4 3 3 3 3 . . . . . . . . .
. . . 1 1 3 3 3 3 3 3 . . . . . . . . .
. . . . . 3 3 3 3 3 3 . . . . 2 2 2 2 .
. . . . . 3 3 3 3 3 3 . . . . 2 2 2 2 .
. . . . . . . . . . . . . . . 2 2 2 2 .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Nokta(0, 0) konumunda dörtgen yok
3 numaralı dörtgen serbest değil
4 numaralı dörtgen silindi
3 numaralı dörtgen silindi
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . 1 1 1 1 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . 2 2 2 2 .
. . . . . . . . . . . . . . . 2 2 2 2 .
. . . . . . . . . . . . . . . 2 2 2 2 .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
'
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]
Permalink
Reply
