26. PUŽ - REŠENJE ZADATKA
Tekst zadatka:
/*
Nemanja ima 6 godina i počeo je da uči da čita i piše. Od strica je dobio vežbanku za učenje slova u kojoj se nalazi vežbica "Puž". Naime u ovoj vežbici postoji tabela dimenzija n x m u koju je potrebno upisati neku rečenicu na sledeći način:
kreće se iz gornjeg levog ugla tabele i upisuju se slova ka desnoj ivici tabele dokle može. Kada se stigne do ivice onda se nastavlja
upisivanje na dole do ivice, zatim na desno do ivice, pa na gore dok ima mesta, onda opet na desno i tako dok se ne popuni cela tabela (slika).
U tabelu se upisuju samo slova, ignorišu se razmaci, znakovi interpunkcije i slično. Pošto je Nemanja suviše mali za ovu vežbu, tabelu je popunio stric. Nemanju sada zanima da li se u rečenici koja je korišćena da se popuni tabela nalazi ime njegovog omiljenog superheroja.
Pošto Nemanja još ne zna sva slova, pomozite mu da ovo otkrije.
Ulaz
U prvom redu standardnog ulaza se nalaze dva cela broja n i m (2≤n,m≤50) koja redom predstavljaju broj redova i broj kolona ove tabele. U narednih n redova se nalazi po m karaktera (mala slova engleske abecede) koji svi zajedno predstavljaju popunjenu tabelu. U narednom redu se nalazi niska karaktera (dužine do 30) koja predstavlja ime Nemanjininog omiljenog superheroja (takođe mala slova engleske abecede, bez razmaka i znakova interpunkcije).
Izlaz
U jedinom redu standardnog izlaza ispisati jedan ceo broj koji predstavlja poziciju u rečenici od koje počinje ime traženog superheroja. U slučaju da ime ne postoji ispisati -1. Ukoliko se ime pojavljuje više puta, ispisati početnu poziciju prvog pojavljiavanja.
se ne pojavljuje jer je njeno ime u rečenici u padežu (akuzativu).
Nemanja ima 6 godina i počeo je da uči da čita i piše. Od strica je dobio vežbanku za učenje slova u kojoj se nalazi vežbica "Puž". Naime u ovoj vežbici postoji tabela dimenzija n x m u koju je potrebno upisati neku rečenicu na sledeći način:
kreće se iz gornjeg levog ugla tabele i upisuju se slova ka desnoj ivici tabele dokle može. Kada se stigne do ivice onda se nastavlja
upisivanje na dole do ivice, zatim na desno do ivice, pa na gore dok ima mesta, onda opet na desno i tako dok se ne popuni cela tabela (slika).
U tabelu se upisuju samo slova, ignorišu se razmaci, znakovi interpunkcije i slično. Pošto je Nemanja suviše mali za ovu vežbu, tabelu je popunio stric. Nemanju sada zanima da li se u rečenici koja je korišćena da se popuni tabela nalazi ime njegovog omiljenog superheroja.
Pošto Nemanja još ne zna sva slova, pomozite mu da ovo otkrije.
Ulaz
U prvom redu standardnog ulaza se nalaze dva cela broja n i m (2≤n,m≤50) koja redom predstavljaju broj redova i broj kolona ove tabele. U narednih n redova se nalazi po m karaktera (mala slova engleske abecede) koji svi zajedno predstavljaju popunjenu tabelu. U narednom redu se nalazi niska karaktera (dužine do 30) koja predstavlja ime Nemanjininog omiljenog superheroja (takođe mala slova engleske abecede, bez razmaka i znakova interpunkcije).
Izlaz
U jedinom redu standardnog izlaza ispisati jedan ceo broj koji predstavlja poziciju u rečenici od koje počinje ime traženog superheroja. U slučaju da ime ne postoji ispisati -1. Ukoliko se ime pojavljuje više puta, ispisati početnu poziciju prvog pojavljiavanja.
se ne pojavljuje jer je njeno ime u rečenici u padežu (akuzativu).
|
Primer 1
Ulaz 4 5 mnogo jdrmv aaneo psmil spajdrmen Izlaz 11 Objašnjenje Kada se tabela razvije dobija se niska karaktera mnogovolimspajdrmena, tako da se reč spajdrmen pojavljuje počevši od 11. mesta. Primer 2 Ulaz 5 5 dalis rnuui ccudt oivoi adelg crnaudovica Izlaz -1 Objašnjenje Iako se u rečenici priča o Crnoj udovici, niz karaktera crnaudovica |
|
Rešenje
Prvo se ućitava ceo tekst kao matrica polja gde se u svakom polju smešta odrećen karakter. Matrica je ovde zapravo vektor string podataka, gde svaki string predstavlja jedan red tabela. Zatim se učita i reč koja se pretražuje. Pretraga se vrši linearno i pretražuje se jedan niz koji sadrži ceo tekst, ali se popunjava pravcem koji je prikazan na slici. Promena pravca se vrši kroz do-while petlju, a unutrašnja for petlja služi da se prolazi kroz tekući red ili kolonu i to u smeru koji odgovara tekućem pravcu kretanja. Pravac se menja posle završene for unutrašnje petlje, a analizira se pomoću switch naredbe.
#include <iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
int m,n;
cin>>n>>m;
string superheroj;
vector<string>tabela(n);
/*Učitava tekst red po red, gde je tabela[i] red teksta*/
for(int i=0; i<n; i++)
{
cin>>tabela[i];
}
cin>>superheroj; //Učitava reč
int tekuciRed=0;
int tekucaKol=m-1;
int pocR=0; /*Početni red, kada se prolazi kroz tekuću kolonu u tabeli i koji predstavlja polje na vrhu kolne, u početku je jednak nuli */
int krajR=n-1; /*Krajnji red, kada se prolazi kroz tekuću kolonu u tabeli i koji predstavlja polje na dnu kolne, u početku je jednak n-1*/
int pocK=0; /*Indeks početne kolone, kada se prolazi kroz tekući red u tabeli i koji predstavlja polje na početku reda i u početku je jednako nuli */
int krajK=m-1; /*Indeks krajnje kolone, kada se prolazi kroz tekući red u tabeli i koji predstavlja polje na kraju reda i inicijalizovan je na nula */
int pravac=1;
string text="";
int pos=-1; //Pozicija koja se traži
/*Menja se pravac kretanja kroz tabelu u svakom ciklusu do-while petlje*/
do
{
switch(pravac) //Analizira pravac
{
case 1: //Pravac je desno
{
/*prolazak kroz kolonu između početnog i krajnjeg reda*/
for(int i=pocK; i<=krajK; i++)
{
text+= tabela[tekuciRed][i]; //Dodaje se tekst iz tekućeg reda na predhodni
}
pocR++; //Pomera početak tekućeg reda za jedno mesto u desno
tekuciRed=krajR; //sledeci red ce biti za 1 nize
}
break;
case 2://Pravac je dole
{
for(int i=pocR; i<=krajR; i++)
{
text += tabela[i][tekucaKol]; //Dodaje se tekst iz tekuće kolone na predhodnu
}
krajK--; //Pomera kraj tekuće kolone za jedno mesto na više
tekucaKol=pocK; //sledeci red ce biti za 1 nize
}
break;
case 3://Pravac je levo
{
for(int i=krajK; i>=pocK; i--)
{
text += tabela[tekuciRed][i]; //Dodaje se tekst iz tekućeg reda na predhodni
}
krajR--; //Pomera kraj tekućeg reda za jedno mesto u levo
tekuciRed=pocR;
}
break;
case 4://Pravac je gore
{
for(int i=krajR; i>=pocR; i--)
{
text += tabela[i][tekucaKol]; //Dodaje se tekst iz tekuće kolone na predhodnu
}
pocK++; //Pomera početak tekuće kolone za jedno mesto na dole
tekucaKol=krajK; //sledeci red ce biti za 1 nize
}
break;
}
pravac++; //menja pravac u smeru kazaljke na satu
pravac=pravac%4; //Može da ima najviše 4 pravca, 5. je u stvari opet prvi
if(pravac==0)pravac=4;
}
while(krajK >= pocK && krajR >= pocR); //Dok se ne podudare početak i kraj tekućeg reda ili početak i kraj tekuće kolone
/* Traži poziciju podstringa superhejor unutar celog teksta*/
pos=text.find(superheroj);
if(pos!=-1)
cout<<pos+1<<endl;
else
cout<<pos<<endl;
return 0;
}
#include<vector>
#include<string>
using namespace std;
int main()
{
int m,n;
cin>>n>>m;
string superheroj;
vector<string>tabela(n);
/*Učitava tekst red po red, gde je tabela[i] red teksta*/
for(int i=0; i<n; i++)
{
cin>>tabela[i];
}
cin>>superheroj; //Učitava reč
int tekuciRed=0;
int tekucaKol=m-1;
int pocR=0; /*Početni red, kada se prolazi kroz tekuću kolonu u tabeli i koji predstavlja polje na vrhu kolne, u početku je jednak nuli */
int krajR=n-1; /*Krajnji red, kada se prolazi kroz tekuću kolonu u tabeli i koji predstavlja polje na dnu kolne, u početku je jednak n-1*/
int pocK=0; /*Indeks početne kolone, kada se prolazi kroz tekući red u tabeli i koji predstavlja polje na početku reda i u početku je jednako nuli */
int krajK=m-1; /*Indeks krajnje kolone, kada se prolazi kroz tekući red u tabeli i koji predstavlja polje na kraju reda i inicijalizovan je na nula */
int pravac=1;
string text="";
int pos=-1; //Pozicija koja se traži
/*Menja se pravac kretanja kroz tabelu u svakom ciklusu do-while petlje*/
do
{
switch(pravac) //Analizira pravac
{
case 1: //Pravac je desno
{
/*prolazak kroz kolonu između početnog i krajnjeg reda*/
for(int i=pocK; i<=krajK; i++)
{
text+= tabela[tekuciRed][i]; //Dodaje se tekst iz tekućeg reda na predhodni
}
pocR++; //Pomera početak tekućeg reda za jedno mesto u desno
tekuciRed=krajR; //sledeci red ce biti za 1 nize
}
break;
case 2://Pravac je dole
{
for(int i=pocR; i<=krajR; i++)
{
text += tabela[i][tekucaKol]; //Dodaje se tekst iz tekuće kolone na predhodnu
}
krajK--; //Pomera kraj tekuće kolone za jedno mesto na više
tekucaKol=pocK; //sledeci red ce biti za 1 nize
}
break;
case 3://Pravac je levo
{
for(int i=krajK; i>=pocK; i--)
{
text += tabela[tekuciRed][i]; //Dodaje se tekst iz tekućeg reda na predhodni
}
krajR--; //Pomera kraj tekućeg reda za jedno mesto u levo
tekuciRed=pocR;
}
break;
case 4://Pravac je gore
{
for(int i=krajR; i>=pocR; i--)
{
text += tabela[i][tekucaKol]; //Dodaje se tekst iz tekuće kolone na predhodnu
}
pocK++; //Pomera početak tekuće kolone za jedno mesto na dole
tekucaKol=krajK; //sledeci red ce biti za 1 nize
}
break;
}
pravac++; //menja pravac u smeru kazaljke na satu
pravac=pravac%4; //Može da ima najviše 4 pravca, 5. je u stvari opet prvi
if(pravac==0)pravac=4;
}
while(krajK >= pocK && krajR >= pocR); //Dok se ne podudare početak i kraj tekućeg reda ili početak i kraj tekuće kolone
/* Traži poziciju podstringa superhejor unutar celog teksta*/
pos=text.find(superheroj);
if(pos!=-1)
cout<<pos+1<<endl;
else
cout<<pos<<endl;
return 0;
}
Ovaj zadatak zahteva da simuliramo kretanje puža kroz matricu, odnosno n x m tabelu, kako bismo kreirali niz karaktera bez znakova interpunkcije i razmaka. Zadatak se rešava tako što pratimo kretanje puža u četiri pravca: desno, dole, levo i gore, koristeći promenljive koje upravljaju početkom i krajem redova i kolona. Na kraju, pretražujemo dobijeni niz karaktera kako bismo pronašli poziciju Nemanjinog omiljenog superheroja. Program koristi find() funkciju za pretragu podstringa, a rezultat se ispisuje u skladu sa zadatim pravilima.
Ova implementacija koristi ciklus i logiku pravaca kako bi se obezbedilo da puž pravilno popuni matricu i kreira niz koji odgovara unesenim karakterima.
Ova implementacija koristi ciklus i logiku pravaca kako bi se obezbedilo da puž pravilno popuni matricu i kreira niz koji odgovara unesenim karakterima.
Rešenje 2
Rešenje ovog zadatka zahteva rekonstrukciju rečenice iz zadate tabele dimenzija n×mn \times mn×m tako što se kreće u obliku puža (spiralno), te zatim proveru da li unutar te rečenice postoji ime superheroja. Rešenje može biti implementirano u C++ sledećim koracima:
- Rekonstruišite rečenicu iz matrice u "puž" obliku.
- Izbacite sve nebitne znakove i razmake.
- Pronađite poziciju prvog pojavljivanja imena superheroja u rečenici (ako postoji).
- Ispišite rezultat.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Funkcija koja vraća niz karaktera u spirali iz matrice
vector<char> spirala(vector<vector<char>>& matrica, int redovi, int kolone) {
vector<char> rezultat;
int gornja = 0, donja = redovi - 1, leva = 0, desna = kolone - 1;
// Nastavljamo dok se granice ne preklapaju
while (gornja <= donja && leva <= desna) {
// Krećemo se s leva na desno
for (int i = leva; i <= desna; i++) {
rezultat.push_back(matrica[gornja][i]);
}
gornja++; // Pomeramo gornju granicu nadole
// Krećemo se s gore na dole
for (int i = gornja; i <= donja; i++) {
rezultat.push_back(matrica[i][desna]);
}
desna--; // Smanjujemo desnu granicu
// Krećemo se s desna na levo, ukoliko ima preostalih redova
if (gornja <= donja) {
for (int i = desna; i >= leva; i--) {
rezultat.push_back(matrica[donja][i]);
}
donja--; // Pomeramo donju granicu naviše
}
// Krećemo se s dole na gore, ukoliko ima preostalih kolona
if (leva <= desna) {
for (int i = donja; i >= gornja; i--) {
rezultat.push_back(matrica[i][leva]);
}
leva++; // Pomeramo levu granicu udesno
}
}
return rezultat;
}
int main() {
int redovi, kolone;
cin >> redovi >> kolone; // Učitavamo dimenzije matrice
// Učitavamo matricu karaktera
vector<vector<char>> matrica(redovi, vector<char>(kolone));
for (int i = 0; i < redovi; i++) {
for (int j = 0; j < kolone; j++) {
cin >> matrica[i][j];
}
}
string superheroj;
cin >> superheroj; // Učitavamo ime superheroja
// Kreiramo niz karaktera u spirali iz matrice
vector<char> recenica = spirala(matrica, redovi, kolone);
string kreirana_recenica(recenica.begin(), recenica.end());
// Tražimo poziciju imena superheroja u spirali
size_t pronadjeno = kreirana_recenica.find(superheroj);
if (pronadjeno != string::npos) {
cout << pronadjeno + 1 << endl; // Ispisujemo poziciju (indeks počinje od 1)
} else {
cout << -1 << endl; // Ako nema superheroja, ispisujemo -1
}
return 0;
}
#include <vector>
#include <string>
using namespace std;
// Funkcija koja vraća niz karaktera u spirali iz matrice
vector<char> spirala(vector<vector<char>>& matrica, int redovi, int kolone) {
vector<char> rezultat;
int gornja = 0, donja = redovi - 1, leva = 0, desna = kolone - 1;
// Nastavljamo dok se granice ne preklapaju
while (gornja <= donja && leva <= desna) {
// Krećemo se s leva na desno
for (int i = leva; i <= desna; i++) {
rezultat.push_back(matrica[gornja][i]);
}
gornja++; // Pomeramo gornju granicu nadole
// Krećemo se s gore na dole
for (int i = gornja; i <= donja; i++) {
rezultat.push_back(matrica[i][desna]);
}
desna--; // Smanjujemo desnu granicu
// Krećemo se s desna na levo, ukoliko ima preostalih redova
if (gornja <= donja) {
for (int i = desna; i >= leva; i--) {
rezultat.push_back(matrica[donja][i]);
}
donja--; // Pomeramo donju granicu naviše
}
// Krećemo se s dole na gore, ukoliko ima preostalih kolona
if (leva <= desna) {
for (int i = donja; i >= gornja; i--) {
rezultat.push_back(matrica[i][leva]);
}
leva++; // Pomeramo levu granicu udesno
}
}
return rezultat;
}
int main() {
int redovi, kolone;
cin >> redovi >> kolone; // Učitavamo dimenzije matrice
// Učitavamo matricu karaktera
vector<vector<char>> matrica(redovi, vector<char>(kolone));
for (int i = 0; i < redovi; i++) {
for (int j = 0; j < kolone; j++) {
cin >> matrica[i][j];
}
}
string superheroj;
cin >> superheroj; // Učitavamo ime superheroja
// Kreiramo niz karaktera u spirali iz matrice
vector<char> recenica = spirala(matrica, redovi, kolone);
string kreirana_recenica(recenica.begin(), recenica.end());
// Tražimo poziciju imena superheroja u spirali
size_t pronadjeno = kreirana_recenica.find(superheroj);
if (pronadjeno != string::npos) {
cout << pronadjeno + 1 << endl; // Ispisujemo poziciju (indeks počinje od 1)
} else {
cout << -1 << endl; // Ako nema superheroja, ispisujemo -1
}
return 0;
}
Objašnjenje:
- Funkcija spiralOrder kreira niz karaktera u "puž" obrascu na osnovu zadate matrice.
- Glavni deo programa učitava matricu dimenzija n×mn \times mn×m i ime superheroja.
- Zatim tražimo početnu poziciju imena superheroja unutar dobijene rečenice i ispisujemo je (1-bazirano indeksiranje).