fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Ezt hogy kéne megcsinálni?

Ezt hogy kéne megcsinálni?

Figyelt kérdés

Pythonból ezt a feladatot kaptam:

Adott egy 2D karakter tömb, ami egy táblát reprezentál és egy maximum 100 karakter hosszú szó (string).

Meg kell mondani, hogy a string kirakható-e a táblában lévő kapcsolódó karakterektől. Két karakter akkor kapcsolódó, ha vízszintesen vagy függőlegesen egymással szomszédosak.


Ezt hogy kéne megoldani?

Gondolom a kiindulás az lenne, hogy keresek egy karaktert a táblán, ami megegyezik a szó első karakterével, ez oké, de innen hogyan tovább? Mi van, ha több ilyen karakter is van? Generáljak le minden lehetséges permutációt, vagy mit csináljak?


2020. ápr. 19. 18:32
1 2 ❯
 1/11 anonim ***** válasza:
16%
Ha megvan az első karakter lépj a másodikra és így tovább. Ez azért nem atomfizika..
2020. ápr. 19. 18:35
Hasznos számodra ez a válasz?
 2/11 A kérdező kommentje:

Igen, elméletben könnyű, de mi van, ha pl. mind a 4 szomszédos karakter ugyanaz és lehet a következő lépés? Vagy honnan tudjam pl., hogy adott karaktert már felhasználtam a táblából, ha mondjuk többször előfordul a szóban?

Elméletben valóban annyi az egész, hogy elindulok, aztán ha nem stimmel egy karakter, akkor megpróbálok egy másik utat, de implementálni nem tudom, hogy kéne.

2020. ápr. 19. 18:48
 3/11 A kérdező kommentje:

Most épp ilyesmivel próbálkozok:

[link]

De nem jövök rá hogy kéne, valami mindig rossz.

2020. ápr. 19. 19:44
 4/11 anonim ***** válasza:
52%
Egy verembe teszed a lehetséges feltárt útvonalakat és ha az egyik útvonal megszakad, akkor kiveszed a veremből az utolsó és folytatod a feltárást. Ha megtaláltad az egész stringet, akkor a válasz igen, ha elfogy a verem, mielőtt megtalálnád, akkor a válasz nem.
2020. ápr. 19. 20:30
Hasznos számodra ez a válasz?
 5/11 A kérdező kommentje:
De ha rossz az útvonal és másikat próbálok, akkor mi akadályoz meg, hogy megint a rossz útvonalra menjek? Ha meg valahogy megjelölöm rosszként a rossz útvonal karaktereit vagy koordinátáit, akkor az megint rossz megoldás, mert ha valamelyik rossz útvonal egy karaktere mondjuk része lenne egy jó útvonalnak, akkor azt nem fogom megtalálni.
2020. ápr. 19. 21:19
 6/11 anonim ***** válasza:
52%
Az akadályoz meg benne, hogy a rosszakat nem teszed a verembe, a bejárás meg determinisztikus.
2020. ápr. 19. 21:33
Hasznos számodra ez a válasz?
 7/11 A kérdező kommentje:
Kaptam közben megoldást privátban, köszönöm.
2020. ápr. 19. 21:53
 8/11 anonim ***** válasza:
0%
Ha ez Elte és nézik az időt(hatekonyságot)akkor én dinamikus programozással próbálkoznék elsőre.Ha vetettek ilyet akkor hajrá,ha nem,google vagy geeksforgeeks,tuti fenn van ez is.
2020. ápr. 19. 22:53
Hasznos számodra ez a válasz?
 9/11 anonim ***** válasza:
100%
Ez klasszikus DFS probléma.
2020. ápr. 20. 06:11
Hasznos számodra ez a válasz?
 10/11 anonim ***** válasza:
100%
DP-nek akkor lenne itt értelme szerintem, ha több szót kéne ellenőrizni ugyanabban a táblában.
2020. ápr. 20. 06:22
Hasznos számodra ez a válasz?
1 2 ❯

Kapcsolódó kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »



Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!