Как я могу вычислить сложность моей самой длинной проблемы пути? - PullRequest
Новая
       38

Как я могу вычислить сложность моей самой длинной проблемы пути?

0 голосов
/ 20 мая 2019

Мне нужно найти самый длинный путь, в котором значения точек становятся больше. Сначала я нахожу количество шагов самого длинного пути, а затем использую DFS, чтобы найти все точки на моей карте и посмотреть, предлагают ли они решения с таким количеством шагов.

Когда я запускаю карту, чтобы узнать количество шагов, я знаю, что по крайней мере O (L * C) будет L, а C - размером карты. Но я не могу найти, что делать дальше. 

void dfsRA(VERTICE** mapa, int L, int C, int x1, int y1, int x2, int y2){

    a=0;
    mapa[x2][y2].pre = cnt++;
    int X=x2,Y=y2;


    //Vai procurar os adjacentes no máximo de oito direções
    for(int n=0; n<8;n++){

      if(n==0){
        x2=x1+1;
        y2=y1+1;
      }

      if(n==1){
        x2=x1+1;
        y2=y1;
      }

      if(n==2){
        x2=x1+1;
        y2=y1-1;
      }

      if(n==3){
        x2=x1;
        y2=y1+1;
      }

      if(n==4){
        x2=x1;
        y2=y1-1;
      }

      if(n==5){
        x2=x1-1;
        y2=y1+1;
      }

      if(n==6){
        x2=x1-1;
        y2=y1;
      }

      if(n==7){
        x2=x1-1;
        y2=y1-1;
      }

    //Verifica se o adjacente existe no mapa
    if(x2<L && x2>=0 && y2>=0 && y2<C){
      //Verifica se o adjacente ainda não foi visitado e se o seu valor é estritamente maior
      if(mapa[x2][y2].pre == -1 && mapa[x2][y2].valor>mapa[x1][y1].valor && i>0){
        i--;
        a++;
        auxiliar++;
        mapa[x2][y2].caminho= auxiliar;
        dfsRA(mapa, L, C, x2, y2, x2, y2);
      }}


      x2=X;
      y2=Y;
    }

    //Realiza o backtrack caso chegue a um ponto onde é impossivél continuar
    //e limpa o vetor pre e retira o ponto do caminho(solução)
    if(a==0 && i >0 && arraysize(mapa,L,C)>0){
      mapa[X][Y].caminho= 0;
      auxiliar--;
      mapa[X][Y].pre= -1;
      i++;
    }
}
...