Backtraking- vai um desafio!

A idéia é fazer que um 'robô' ande por uma sala (matriz 10x10), na qual as posiçoes (0,0)(0,1)(1,0)e(1,1) são posiçoes da area de armazenagem.
Em algumas posições da sala coloca-se obstaculos (posicao[x][y]=2)e blocos(posicao[x][y]=3). Os obstaculos nao deixam que o robo passe por la, tendo ele que contornar. Seu objetivo é buscar blocos (4 no total).
A cada posição que passa, começando pela (0,2), o robo deixa uma marca (posicao[x][y]=1).
Entao, pra esclarecer: se posicao[x][y]=0, a posicao esta vazia; se posicao[x][y]=1, o robo ja passou por lá; se posicao[x][y]=2, tem um obstaculo aí; se posicao[x][y]=3, tem um bloco aí.
O robo deve sempre tentar andar para cima. se nao for possivel, deve ir para a direita. se tb nao for possivel, deve ir para baixo. se nao for possivel, deve ir para a esquerda. Se nenhum desses sentidos for permitido (tiver obstaculo, ja tiver passado ou se ficará fora da sala), o robo deve voltar a sua ultima posição.
Quando achar um bloco, o robo devera ir para a area de armazenagem seguindo as marcas (1) que ele deixou (ou seja, voltar por onde passou) e desmarcá-las
E por aí vai...

já fiz o código varias vezes mas não esta dando certo.
Nao o colocarei aqui porque compreende 6 classes, aí acredito que vcs iriam querer me bater shuahsuahushuahsu
Peço que me ajudem a pensar na logica...

Vou colocar aqui só o metodo de busca para vcs verem o que estou errando:

int [][] posicao = new int [10][10];
  int [] px = new int [96]; //o numero de posiçoes a buscar é igual a area da sala (100) menos a area de armazenagem (4)
  int [] py = new int [96];
  int [] dx = {0,1,0,-1};
  int [] dy = {1,0,-1,0};
//posicao[x+dx[0]][y+dy[0]] VAI PRA CIMA
//posicao[x+dx[1]][y+dy[1]] VAI PRA DIREITA
//posicao[x+dx[2]][y+dy[2]] VAI PRA BAIXO
//posicao[x+dx[3]][y+dy[3]] VAI PRA ESQUERDA
  int i = 0;
  int p = 0;
  
  static int qtdBlocosAdicionados = 0;
  static int qtdBlocosAchados = 0;

  
  public boolean buscaBloco(int x, int y)
  { 
    
    if(sala.marcadorEm(x,y) == 3) //se é BLOCO
    {
      posicao[x][y]=1; // marca presença na posicao 
      px[p]= x;
      px[p]= y;
      System.out.println("Bloco recolhido em ("+x+","+y+")");
      
      while( x!=0 || y!=2) //posicao de inicio da busca 
      {
        p=p-1;
        posicao[x][y]=0; //remove a marcacao de presença
        x= px[p];
        y= py[p];
      }
      
      i=0;
      qtdBlocosAchados++;
      
      return  true;
    }
    else
    {
      while(x+dx[i]<10 && y+dy[i]<10) //ERRADO AQUI NÉ?
      {
        x=x+dx[i];
        y=y+dy[i];
        System.out.println("Busca em ("+x+","+y+")");
        buscaBloco(x,y);
        
        
        if(i<dx.length)
        {
          if (posicao[x][y] == 2) //OBSTACULO
          {
            System.out.println("Obstáculo detectado em ("+x+","+y+")");
            x=x-dx[i];
            y=y-dy[i];
            i++;
          }
          else if (! (x >= 0 && x < 10) && (y >= 0 && y < 10)) //POSIÇAO FORA DA SALA
          {
            x=px[p];
            y=py[p];
            i++;
          }
          
          else if (posicao[x][y]==1) //JÁ PASSOU PELA POSICAO
          {
            i++;
          }
          else //POSICAO VAZIA
          {
            posicao[x][y]=1;
            px[p] = x;
            py[p] = y;
            p++;
            i=0;
          }
        }
        else
        {
          posicao[x][y]=1;
          x= px[p];
          y= py[p];            
          i=0; 
          p--;
        }        
      }
      
      return false;
    }
  }

______________________________

public void buscaBlocos()
  {   
      for(x= this.x; x < 10; x++)
      {
        for(y= this.y; y < 10; y++)
        {
          while(p!=px.length)
          {
            buscaBloco(x,y);
          }
        }
      }
    
    System.out.println("Busca terminada. Blocos recuperados.");
  
}

4 Respostas

Topicos relacionados