C Sharp, Aknakereso, Ures mezok vizsgalata, feltaras.
2019-12-13T15:44:46+01:00
2019-12-15T22:20:38+01:00
2022-08-11T16:45:35+02:00
rweber
Sziasztok,

C#/Winform/Aknakereso temaban lennne ismet egy kerdesem.

Aknamentes mezok:  Ha a játékos aknamentes környezetű mezőre kattint, akkor az adott mezőhöz oldal- és sarokhatárosan csatlakozó (aknamentes) mezők mindegyike feltárul, valamint az így feltáruló aknamentes "szigettel" szomszédos mezők is feltárulnak.

Ezt ugy gondoltam megoldani, hogy Csaboka2 altal javasolt , aktualis mezot 3x3-as matrixal bejarom, ha ha aknamentes , felszabaditom, es ha van erteke(nulla eseten ures marad) kiirom, ez meg is lenne.

Viszont ez meg nem eleg, hiszen a nulla erteku(tehat ures) mezok szomszedait is megkell vizsgalni.

Itt akadtam el, most akkor minden nulla erteku mezonek, amit a 3x3 matrixon belul talaltam csinaljak ismet egy sajat 3x3-as matrix keresest,amig el nem fogynak az aknamentes mezok, vagy hogyan tudnam a legegyszerubben feltarni a teljes aknamentes "szigetet"?

A segitseget elore is kosznom!
Mutasd a teljes hozzászólást!
Kevésbé hatékony, de a mélységi és szélességi bejárásnál talán könnyebben érthető algoritmus:

Végigmész a tömbön, és ahol nullás felfedett mezőt látsz, felfeded a szomszédait. Közben egy boolean változóban figyeled, hogy volt-e legalább egy felfedés (értelemszerűen ezt a ciklus előtt hamisra állítod). Ha volt legalább egy felfedés, akkor kezded az egész keresést elölről.

Minden ciklusban fel fogsz fedni valahány mezőt, az elején keveset, aztán egyre többet. Egyszer eljutsz egy olyan állapotba, amikor már minden szükséges mezőt felfedtél, és ekkor nem lesz már több felfedés a ciklusban. Innen tudod, hogy végeztél.

Még egyszer mondom, nem ideális futásidejű a dolog, de egy mai gépen egy aknakereső pályáján nem lesz észlelhető a különbség.
Mutasd a teljes hozzászólást!

  • Keress rá a mélységi és szélességi bejárásokra :)

    Tipikus feladat, amivel lehet ilyesmit gyakorolni és vizualizálni egy erdőtűz implementálása..
    - minden körben leraksz N fát (zöld pixel) és eldobsz egy gyufát.
    - Ha gyufa fát talál felgyújtja, mint ahogy az összes szomszédos fát is. (piros pixel)

    Látványos lesz a két fajta bejárás közti különbség :)
    Mutasd a teljes hozzászólást!
  • Depth-first search mélységi
    Breadth-first search - szélességi
    Mutasd a teljes hozzászólást!
  • Kevésbé hatékony, de a mélységi és szélességi bejárásnál talán könnyebben érthető algoritmus:

    Végigmész a tömbön, és ahol nullás felfedett mezőt látsz, felfeded a szomszédait. Közben egy boolean változóban figyeled, hogy volt-e legalább egy felfedés (értelemszerűen ezt a ciklus előtt hamisra állítod). Ha volt legalább egy felfedés, akkor kezded az egész keresést elölről.

    Minden ciklusban fel fogsz fedni valahány mezőt, az elején keveset, aztán egyre többet. Egyszer eljutsz egy olyan állapotba, amikor már minden szükséges mezőt felfedtél, és ekkor nem lesz már több felfedés a ciklusban. Innen tudod, hogy végeztél.

    Még egyszer mondom, nem ideális futásidejű a dolog, de egy mai gépen egy aknakereső pályáján nem lesz észlelhető a különbség.
    Mutasd a teljes hozzászólást!
  • Koszonom az otletet, ezen azt hiszem meg ragodni fogok egy darabik, amig teljesen magameva tudom tenni... :)
    Mutasd a teljes hozzászólást!
  • Koszonom, ezen a vonalon fogok elindulni!
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd