Tarkoituksena olisi tehdä semmoinen sanaristikko, mitä joskus televisiostakin näkee, missä etsitään sanoja 10x10 kirjainruudukosta. Tässä onkin 15x15 ruudukko, mutta en keksi mitään algoritmia noiden sanojen etsimiseen. Eli jos käyttäjän syöttämän sanan ensimmäinen kirjain löytyy ruudukosta, niin etsitään sanan toinen kirjain joko ensimmäisen ylhäältä, alhaalta, vasemmalta tai oikealta. Jos toinen kirjain löytyy oikealta, voidaan etsiä kolmatta kirjainta ylhäältä, alhaalta ja oikealta, koska ei voida kääntyä enää takaisin. (Tämä siis estää esim. sanan "hah" löytymistä vierekkäin tai päällekkäin olevista H- ja A-kirjaimista.) Jos kolmatta kirjainta ei löydetäkään, joudutaankin palaamaan ensimmäiseen kirjaimeen ja etsimään taas toista kirjainta eri suunnasta.
Asiaa selventää vielä oheinen, varmaankin riittävän kommentoitu, lähdekoodi.
#include <iostream>
#include <sys/timeb.h> // käytetään millisekunteja aika_nyt:ssa
using namespace std;
long rnd(long eka, long toka);
void aika(double sekunnit);
long double aika_nyt();
string suurenna(string teksti);
int main()
{
string input; // käyttäjän löytämä sana
bool loytyy = false; // löydettiinkö sana
char ristikko[15][15]; // 15x15 kirjainristikko, josta sitten etsitään sanoja
for (int y = 0; y < 15; y++)
{
for (int x = 0; x < 15; x++)
{
do
{
ristikko[x][y] = (char)rnd(65, 87); // arvotaan ristikkoon kirjaimet A-V
} while (ristikko[x][y] == 'Q' || // emme halua ristikkoon Q:ta
ristikko[x][y] == 'C' || // eikä C:tä
ristikko[x][y] == 'F'); // eikä myöskään F:ää
aika(0.001); // odotetaan hetki, ettei tule samoja kirjaimia peräkkäin
}
}
while (input != "/LOPETA")
{
cout<<endl;
for (int y = 0; y < 15; y++)
{
for (int x = 0; x < 15; x++)
{
cout<<" "<<ristikko[x][y]; // tulostetaan ristikko
}
cout<<endl<<endl;
}
if (loytyy)
cout<<"Hienoa, l\x94ysit sanan!"<<endl;
cout<<"Lopeta ohjelma kirjoittamalla \"/lopeta\". Sanan tulee olla yli 2 kirjainta pitk\x84."<<endl;
do
{
cout<<(char)175<<" ";
cin>>input; // käyttäjä syöttää löytämänsä sanan tai "/lopeta", jolloin ohjelma lopetetaan
} while (input.length() <= 2);
input = suurenna(input);
for (int y = 0; y < 15; y++)
{
for (int x = 0; x < 15; x++)
{
if (ristikko[x][y] == input[0]) // ensimmäinen kirjain löydetty
{
//hakualgoritmi
}
else
loytyy = false;
}
}
system("cls"); // pyyhitään ruudulta vanhat tekstit pois
}
return 0;
}
long rnd(long eka, long toka)
{
static bool alustettu = false;
long palaute = 0;
if (!alustettu)
{
alustettu = true;
srand(aika_nyt() * 1000);
}
palaute = rand() % (toka - eka) + eka;
return palaute;
}
void aika(double sekunnit)
{
long double aika1 = aika_nyt();
while (aika_nyt() - aika1 <= sekunnit) {}
}
long double aika_nyt()
{
time_t sekunnit = time (NULL);
_timeb aika;
_ftime(&aika);
long double palaute = (long double)sekunnit + (long double)aika.millitm / 1000;
return palaute;
}
string suurenna(string teksti)
{
for (int ind = 0; ind < teksti.length(); ind++)
teksti[ind] = (char)toupper(teksti[ind]);
return teksti;
}Koska sanat eivät kuitenkaan ole kovin pitkiä, voit käyttää syvyyssuuntaista (rekursiivista) hakua. Jokaisesta ruudusta lähtien siis tutkitaan vuorotellen jokainen reitti aina siihen asti, että kirjain ei täsmää sanaan. Jos päästään viimeiseen kirjaimeen asti, ratkaisu on valmis. Kas näin:
std::string sana;
char merkit[15][15];
bool kayty[15][15] = {{false}};
bool haku(int x, int y, int n)
{
// Tarkistetaan rajat
if (x < 0 || x >= 15 || y < 0 || y >= 15) {
return false;
}
// Tarkistetaan, ettei ole jo käyty tässä ja että merkki sopii
if (kayty[x][y] || merkit[x][y] != sana[n]) {
return false;
}
// Jos tämä on viimeinen kirjain, palautetaan tosi
if (n == (int)sana.length() - 1) {
return true;
}
// Merkitään ruutu käydyksi ja jatketaan hakua joka suuntaan
kayty[x][y] = true;
bool loytyiko = haku(x+1, y, n+1) || haku(x-1, y, n+1) || haku(x, y+1, n+1) || haku(x, y-1, n+1);
// Jos reitti pitäisi ottaa talteen, tässä vaiheessa olisi syytä tarkistaa, löytyikö vastaus, ja jos löytyi, pitäisi lisätä listaan tämä ruutu.
// Palataan haussa taaksepäin, siis tässä ei ole "vielä" käyty
kayty[x][y] = false;
// Kerrotaan, oliko täällä ratkaisu
return loytyiko;
}
// for (x...) for (y...) if (haku(x, y, 0)) std::cout << "kohdassa (" << x << ", " << y << ") on sana!" << std::endl;(Muoks. Huom! Tämä vastaus koskee tilannetta, jossa sanan suunta ei saa muuttua. Olisi pitänyt lukea kysymys ennen vastaamista. Mutta Metabolixin koodi toimii juuri oikein.)
Tietystä kirjaimesta alkavan sanan voi helpoiten tunnistaa rekursion avulla. Sana voi kulkea joko ylös, alas, vasemmalle tai oikealle, ja jokainen suunta tutkitaan erikseen rekursiivisella funktiolla. Tämä funktio rakentuu niin, että pidetään kirjaa, kuinka monta sanan kirjainta on tunnistettu, missä ruudukon kohdassa ollaan ja mihin suuntaan liikutaan. Jos joudutaan ruudukon rajojen ulkopuolella tai kirjain on väärä, etsintä päättyy. Jos päästään sanan loppuun asti, sana on löytynyt.
Esimerkkikoodi selventää asiaa:
#include <stdio.h>
#define LEVEYS 5
#define KORKEUS 5
char sanat[KORKEUS][LEVEYS] =
{{'S','N','P','H','H'},
{'U','E','O','K','S'},
{'B','K','W','U','J'},
{'Z','W','B','Y','J'},
{'N','Y','B','P','M'}};
char sana[] = "KOE";
int pituus = 3;
void etsi(int kohta, int x, int y, int xs, int ys) {
/* etsintä on päättynyt ja sana löytynyt */
if (kohta == pituus) {
printf("Sana alkaa rivillä %i sarakkeessa %i!\n",
y - ys * pituus + 1, x - xs * pituus + 1);
return;
}
/* poistutaan, jos ollaan rajojen ulkopuolella */
if (x < 0 || x >= LEVEYS) return;
if (y < 0 || y >= KORKEUS) return;
/* poistutaan, jos ruudukon kirjain on väärä */
if (sana[kohta] != sanat[y][x]) return;
/* jatketaan etsintää seuraavaan kirjaimeen */
etsi(kohta + 1, x + xs, y + ys, xs, ys);
}
int main(void) {
int x, y;
for (y = 0; y < KORKEUS; y++) {
for (x = 0; x < LEVEYS; x++) {
etsi(0, x, y, 0, -1); /* ylös */
etsi(0, x, y, 0, 1); /* alas */
etsi(0, x, y, -1, 0); /* vasemmalle */
etsi(0, x, y, 1, 0); /* oikealle */
}
}
return 0;
}Esimerkiksi sana KOE löytyy ruudukosta seuraavasti:
1. Kutsutaan funktiota: etsi(0, 3, 1, -1, 0). Kirjaimet sana[0] ja sanat[1][3] ovat samat (K), joten etsintä jatkuu.
2. Kutsutaan funktiota: etsi(1, 2, 1, -1, 0). Kirjaimet sana[1] ja sanat[1][2] ovat samat (O), joten etsintä jatkuu.
3. Kutsutaan funktiota: etsi(2, 1, 1, -1, 0). Kirjaimet sana[2] ja sanat[1][1] ovat samat (E), joten etsintä jatkuu.
4. Kutsutaan funktiota: etsi(3, 0, 1, -1, 0). Koko sana on nyt löytynyt.
Toinen tapa olisi käyttää neljää peräkkäistä for-silmukkaa, jotka etsivät sanaa ylhäältä, alhaalta, vasemmalta ja oikealta, mutta koodia tarvittaisiin jonkin verran enemmän. Lisäksi jos etsintään täytyy tehdä myöhemmin pieniä muutoksia (esim. sanat saavat kulkea myös vinoon), rekursiota käyttämällä niistä selviää usein helpolla.
(Muoks. Tästä tulikin malliesimerkki siitä, miten helposti koodin toimintaa voi muuttaa. Kun funktio kutsuukin itseään joka suuntaan ja pitää kirjaa sanan alkuosaan kuuluvista ruuduista, eli se muutetaan Metabolixin funktion kaltaiseksi, ohjelma toimii niin kuin alun perin haluttiin.)
joo jee hienoa toimii kiitos!
Aihe on jo aika vanha, joten et voi enää vastata siihen.