Próba optymalizacji

0

Witam, napisałem taki kod i mam pytanie czy jest możliwość jeszcze bardziej go zoptymalizować?

 #include <iostream>
#include <string>

using namespace std;

string *plansza;
string pytanie;
string *odp;

unsigned long long int size, p, N, M;

void rek(long long int n, long long int m, unsigned long long int i=0)
{
    if(i==size)
    {
        if(plansza[n][m]==pytanie[i])
        {
            odp[p]="TAK";
        }
        else
        {
            if(odp[p]!="TAK") odp[p]="NIE";
        }
        return;
    }
    if(n-1>=0 && pytanie[i+1]==plansza[n-1][m]) rek(n-1,m, i+1);
    if(m-1>=0 && pytanie[i+1]==plansza[n][m-1]) rek(n,m-1, i+1);
    if(n+1<N && pytanie[i+1]==plansza[n+1][m]) rek(n+1,m, i+1);
    if(m+1<M && pytanie[i+1]==plansza[n][m+1]) rek(n,m+1, i+1); 
}

void func(unsigned long long int i)
{
    unsigned long long int m, n;
    for(n=0;n<N;n++)
    {
        for(m=0;m<M;m++)
        {
            if(plansza[n][m]==pytanie[0])
            {
                rek(n,m);
                if(odp[i]=="TAK") return;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    unsigned long long int P, i;
    cin>>N>>M;
    plansza=new string[N];
    for(i=0;i<N;i++)
    {
        cin>>plansza[i];
    }
    cin>>P;
    odp=new string[P];
    for(i=0;i<P;i++)
    {
        cin>>pytanie;
        p=i;
        odp[p]="NIE";
        size=pytanie.size()-1;
        func(i);
    }
    for(i=0;i<P;i++)
    {
        cout<<odp[i]<<endl;
    }
    return 0;
}
0

Co ten kod w ogóle robi?

0

To rozwiązanie zadania z VII OIG pt."Literki".

Tu jest treść:
Jas i Małgosia graja w nietypowa gre. Rozkładaja na podłodze wielka plansze,
na której role pól spełniaja literki. Na zmiane podaja słowa i otrzymuja punkty,
jesli da sie te słowa utworzyc wodzac palcem po planszy (jesli da sie je przedstawic
jako ciag pól sasiadujacych bokami). Niektóre ze słów sa naprawde długie i dzieci
nie potrafia same tego sprawdzic. Pomozesz im?

  • Wejscie
    W pierwszym wierszu standardowego wejscia zapisano dwie liczby N i M (1 6 N; M 6 100), oznaczajace
    wymiary planszy. W kolejnych N wierszach znajduje sie po M małych liter alfabetu angielskiego — jest to
    przedstawienie planszy. W nastepnym wierszu pojawi sie jedna liczba P, oznaczajaca liczbe pytan dzieci.
    W kazdym z kolejnych P wierszy pojawi sie jedno słowo złozone z małych liter alfabetu angielskiego — słowo,
    o które pytaja Jas i Małgosia. Suma długosci wszystkich słów nie przekroczy 1 000.

  • Wyjscie
    Na wyjscie nalezy wypisac P wierszy — w i-tym wierszu odpowiedz dla i-tego pytania. Jesli słowo pojawia sie
    na planszy nalezy wypisac „TAK”, w przeciwnym wypadku nalezy wypisac „NIE”.

0

Ja bym zapytał czy da się to napisać wolniej niż to co tu zrobiłeś i wydaje mi się że osiągnąłeś "dno" ;]
Użycie rekurencji totalnie zabija to rozwiązanie, gdybyś chociaż iterowal tutaj (na zasadzie BFSa) to może by to jakoś dało radę, ale tak? o_O
Ja bym proponował użyć tutaj jakiejś sensownej struktury danych, opartej o hash-mape:

  • dla każdej literki mamy listę pozycji na planszy gdzie ona występuje
  • dla każdej pozycji na planszy mamy listę przylegających do niej pozycji z literkami
    W ten sposób możesz zadanie rozwiązać w czasie liniowym względem sumarycznej dlugości słów, a skoro ich długość jest ograniczona z góry przez stałą, to w sumie zadanie zostanie rozwiązane w czasie O(1) ;]
    Ale jeszcze raz podkreślam -> nie rób tu jawnej rekurencji, tylko zrób to iteracyjnie.
0

Dzięki @Shalom, to mój kolejny sukces z tym dnem

0

Ale sam algorytm jest poprawny i da dobry wynik??

0

Tego to nie wiem, ale przecież tutaj rozwiązanie jest proste jak budowa cepa i nie wiem gdzie mógłbyś się pomylić w algorytmie...

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0