• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Warrior

[1] Labirinto digital - Dificuldade média

8 mensagens neste tópico

Título:

Labirinto Digital

Objectivo:

Fazer um pequeno programa/função que encontre a distância mais curta entre dois pontos num labirinto num formato pré-estabelecido.

O labirinto é visto como uma matriz N por M, onde a célula (i,j) contem um número que indica quais das quatro paredes que envolvem a célula estão de pé e é uma soma de 4 inteiros.

  • 1: parede a oeste
  • 2: parede a norte
  • 4: parede a este
  • 8: parede a sul

Exemplo:

7 - célula com 3 paredes: oeste, norte e este.

O labirinto é sempre válido.

O labirinto está sempre limitado por paredes.

Alem do labirinto, são fornecidos 2 pontos: pretende-se o caminho mais curto do primeiro para o segundo.

Deve ser criada ou uma função que recebe um labirinto e os dois pontos e retorna a distância mais curta, ou um programa completo que faça o pedido.

Exemplo de input/output

Input:

3 3

7 15 7

5 15 5

9 10 12

1 1

1 3

Output:

6

Explicação:

Labirinto 3 por 3.

Dois pontos, (1,1) e (1,3).

Um labirinto:

  _  _  _

|  | _ |  |

|  | _ |  |

| _  _  _ |

O caminho mais curto envolve 6 passos.

Material de apoio:

Em algumas linguagens pode ser necessária uma biblioteca para operações bit-a-bit.

Restrições:

O programa deve gerar a solução por outro método que não brute-force.


Discussão do problema em:

http://www.portugal-a-programar.pt/index.php?showtopic=16509


Soluções Enviadas

mogers - C++

pcaldeira - C

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui vai a minha solução em C++. Assumo que o labirinto dado é válido, com informação consistente. Isto é, se em (2,3) não tenho parede à direita, em (2,4) não existe parede à esquerda.

O algoritmo usado é uma Breath-First-Search normal. O estado da pesquisa é guardado em pair's de modo a tornar o código mais compacto.

#include <iostream>
#include <queue>
#define Oeste	1
#define Norte	2
#define Este	4
#define Sul	8
#define Y	first
#define X	second
#define not_contains(Set , X)	( ( (Set) & (X) ) == 0 )
using namespace std;

void add2queue( int ** maze , bool ** v , queue<pair<int,int> > & q , int Dir , int cY , int cX , int nY, int nX )
{
if ( not_contains(maze[ cY ][ cX ] , Dir ) && (!v[ nY ][ nX ] ) )
	q.push( make_pair( nY , nX ) );
}
int main()
{						// vars
bool found = false , **visit ;
int Nlinhas , Ncolunas , i , j , movimentos = -1 , **maze;
pair<int,int> current , destino;
					// input
cin >> Nlinhas >> Ncolunas;	
maze = new int * [Nlinhas];
visit = new bool * [Nlinhas];

for ( i = 0 ; i < Nlinhas ; i++ ) {
	maze[i] = new int[Ncolunas];
	visit[i] = new bool[Ncolunas];
	memset( visit[i] , false , sizeof(bool) * Ncolunas );
	for ( j = 0 ; j < Ncolunas ; j++ )
		cin >> maze[i][j];
}	
cin >> current.Y >> current.X >> destino.Y >> destino.X;
destino.Y-- ; destino.X-- ;
					// bfs
queue< pair<int,int> > q;	
q.push( make_pair( current.Y - 1 , current.X - 1 ) );

while ( ! q.empty() && !found)
{
	movimentos++;
	queue< pair<int,int> > q2;
	while ( ! q.empty() && !found)
	{
		current = q.front();
		q.pop();
		if (current == destino)
			found = true;
		else if ( visit[ current.Y ][ current.X ] == false )
		{
			visit[ current.Y ][ current.X ] = true;

			add2queue( maze , visit , q2 , Norte , current.Y , current.X , current.Y-1 , current.X );
			add2queue( maze , visit , q2 , Sul   , current.Y , current.X , current.Y+1 , current.X );
			add2queue( maze , visit , q2 , Oeste , current.Y , current.X , current.Y   , current.X-1 );
			add2queue( maze , visit , q2 , Este  , current.Y , current.X , current.Y   , current.X+1 );
		}
	}
	q = q2;
}
cout << movimentos << endl;
return 0;
}

PS: não podem mudar as cores do GeSHI para C++? Este azul bebé dá cabo dos olhos :s

Edit: Acho que está mais legivel assim.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, cá está a minha solução em C. O código não está nada elegante nem pequeno (nem optimizado) mas tentei espaçá-lo e separar secções para tornar mais legível. Enfim,  funciona, é o que interessa. O algoritmo é um BFS simples. Para labirintos com mais de 10 unidades de lado, alterar o LIMIT na primeira linha.

#define LIMIT 10
#include <stdio.h>

//declarations
int width, height, init[2], end[2];
int maze[LIMIT][LIMIT];
int seen[LIMIT][LIMIT];
int stop=0;

typedef struct {
int pos[2], steps;
} path;

path queue[LIMIT*LIMIT];
int queue_ins=0;
int queue_ret=0;

//path and queue operations
path move(path origin, int direction) //1 left, 2 up, 3 right, 4 down
{
switch(direction) {
	case 1: origin.pos[1]-=1; break;
	case 2: origin.pos[0]-=1; break;
	case 3: origin.pos[1]+=1; break;
	case 4: origin.pos[0]+=1; break;
	default: break;
}
origin.steps++;
return origin;
}

void queue_insert(path a) {
queue[queue_ins] = a;
queue_ins++;
}

path queue_retrieve() {
queue_ret++;
return queue[queue_ret-1];
}

int queue_empty() {
return (queue_ins==queue_ret) ? 1 : 0;
}	

//bfs
void process(path a)
{
int dirs[4] = {1, 2, 4, 8};
int i;

if (seen[a.pos[0]][a.pos[1]]) return;

if (a.pos[0]==end[0] && a.pos[1]==end[1]) 
{
	printf("%d", a.steps);
	stop=1;
	return;
}

seen[a.pos[0]][a.pos[1]]=1;

for(i=0; i<4; i++)
{
	if( !(maze[a.pos[0]][a.pos[1]] & dirs[i]) )
		queue_insert(move(a, i+1));
}
}

void bfs()
{
while(!stop)
	process(queue_retrieve());
}

int main()
{
//input and initializations
int i, j;
scanf("%d %d", &width, &height);
for(i=0; i<height; i++)
	for(j=0; j<width; j++)
		scanf("%d", &maze[i][j]);
scanf("%d %d", &init[0], &init[1]);
scanf("%d %d", &end[0], &end[1]);

init[0]--; init[1]--; end[0]--;  end[1]--;

path start;
start.steps=0;
start.pos[0]=init[0];
start.pos[1]=init[1];

queue_insert(start);
bfs();

return 0;
}

PS - Além do que o mogers assumiu, também assumo que nos limites do labirinto existem paredes (o programa não verifica boundaries).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

C++, algoritmo recursivo. Não fiz testes intensivos, mas experimentei algumas variações e não encontrei erros. Lê o input de um ficheiro com o nome labirinto.txt

#include <fstream>
#include <iostream>

using namespace std;

int *casas, w, h, fimx, fimy, ncasas;
char *visited; //array de casas visitadas

int encontraCaminho(int x, int y, int prev = 0) {
if (x==fimx && y==fimy) return 0; //chegou ao destino
if (visited[x*w+y] == 1) return ncasas; //casa já visitada

visited[x*w+y] = 1; //marcar casa como visitada

int myconta=ncasas, curconta=0;

if (((casas[x*w+y] & 1) == 0) && (prev != 1)) { // não há parede a oeste
	myconta = encontraCaminho(x-1, y, 4);
}
if (((casas[x*w+y] & 2) == 0) && (prev != 2)) { // não há parede a norte
	curconta = encontraCaminho(x, y-1, 8);
	if (curconta < myconta) myconta=curconta;
}
if (((casas[x*w+y] & 4) == 0) && (prev != 4)) { // não há parede a este
	curconta = encontraCaminho(x+1, y, 1);
	if (curconta < myconta) myconta=curconta;
}
if (((casas[x*w+y] & 8) == 0) && (prev != 8)) { // não há parede a sul
	curconta = encontraCaminho(x, y+1, 2);
	if (curconta < myconta) myconta=curconta;
}
visited[x*w+y] = 0; //desmarcar visita da casa (possivelmente desnecessário, e possível ganho de performance)
return myconta+1;
}

int main() {
ifstream labfile("labirinto.txt");
if (!labfile) {
	cout << "labirinto.txt nao encontrado." << endl;
	return 1;
}

labfile >> w >> h;
ncasas = w*h;
casas = new int[ncasas];
visited = new char[ncasas];
memset(visited, 0, ncasas);

for (int i=0; i<w; ++i)
	for (int j=0; j<h; ++j)
		labfile >> casas[j*w+i];

int iniciox, inicioy;

labfile >> inicioy >> iniciox >> fimy >> fimx;

--fimx; --fimy;
cout << "Caminho mais curto leva: " << encontraCaminho(--iniciox, --inicioy) << " passos\n";

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

é uma classe em java que recebe um array bidimensional como labirinto, um array com os pontos de origem e outro array com os pontos de destino!

Nao testei mt bem a classe por falta de tempo, tanto que nem fiz a leitura dos dados :/

import java.util.LinkedList;
import java.util.Queue;

public class LabirintoDigital {
  
    private static class node{
        
        private int x,y;
        private int nivel;
        private int anterior;
        
        private node (int x , int y ,int nivel, int anterior){
            this.x = x;
            this.y = y;
            this.anterior = anterior;
            this.nivel = nivel;
           
        }
        
        public boolean equals(node outro){
            return (outro.x == this.x) && (outro.y == this.y);
        }
    }
    
    private  Queue<node> lista = new LinkedList<node>();
    private  int [][] labirinto;
    
    private int nPassos(node pontoD){
     
        if(lista.peek().equals(pontoD))
            return lista.poll().nivel;
        else{
            proximoPasso(labirinto[lista.peek().x - 1][lista.peek().y - 1],lista.poll());
            return nPassos(pontoD);
        }
            
    }
             
    private void proximoPasso(int celua ,node pontos){

        int direcao = 15 - celua - pontos.anterior;
        
        if(direcao >= 8){
            direcao -= 8;
            lista.offer(new node(pontos.x + 1, pontos.y , pontos.nivel + 1, 2 ));
        }
        if(direcao >= 4){
            lista.offer(new node(pontos.x , pontos.y + 1 , pontos.nivel + 1, 1 ));
            direcao -= 4;
        }
        if(direcao >= 2){
            lista.offer(new node(pontos.x - 1 , pontos.y , pontos.nivel + 1, 8 ));
            direcao -= 2;
        }
        if(direcao >= 1){
            lista.offer(new node(pontos.x , pontos.y - 1 , pontos.nivel + 1 , 4 ));
            direcao -= 1;
        }
    }

    public LabirintoDigital(int[][] labirinto, int[] pontosO, int[] pontosD) {
        this.labirinto = labirinto;
        lista.offer(new node(pontosO[0],pontosO[1], 0, 0));
        System.out.println("O caminho mais curto: "+ nPassos(new node(pontosD[0],pontosD[1],0,0)));
    }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas...  :cheesygrin:

Explicaçao do código:

A array branches servirá pra alojar o endpoint de cada ramo, e a array multidimensional Table possui a informaçao do labirinto (paredes e casas já usadas).

Começando pelo ponto de origem, efectua-se um passo de cada vez para cada ramo existente na array branches.

São criados sub-ramos a partir dos movimentos possíveis. O primeiro sub-ramo substitui o ramo antigo, os restantes são adicionados à array branches.

Caso determinado ramo não se mova, será eliminado. O código termina quando deixarem de existir ramos (se total for 0) ou quando um ramo atingir o destino.

Exemplo:

input.txt:

3 3

3 10 6

5 15 5

9 10 12

1 1

2 3

Lista de ramos em cada iteracção do loop exterior da função GetSteps():

1,1

2,1 / 1,2

3,1 / 1,3

3,2 / 2,3

#include <stdio.h>

#define FILENAME "input.txt"
#define BRANCH_MAX 256

#define INACTIVE 16

#define WALL_NORT 2
#define WALL_SOUTH 8
#define WALL_EAST 4
#define WALL_WEST 1

#define MOVE_UP 1
#define MOVE_DOWN 2
#define MOVE_LEFT 3
#define MOVE_RIGHT 0

struct POINT {
int row;
int col;
};

struct MOVES{
char wall;
char row;
char column;
};

const struct MOVES MovesList[4] = {
{ WALL_EAST, 0, 1 },          // MOVE_RIGHT
{ WALL_NORT, -1, 0 },         // MOVE_UP
{ WALL_SOUTH, 1, 0 },         // MOVE_DOWN
{ WALL_WEST, 0, -1 }          // MOVE_LEFT
};

char **Table;
struct POINT *branches, end;
int total;

int MakeMove(struct POINT *src, int b, int m, char *update)
{
  struct POINT dest;
  
  if (!(Table[src->row][src->col] & MovesList[m].wall))
  {
    dest.row = src->row + (int)MovesList[m].row;
    dest.col = src->col + (int)MovesList[m].column;
    
    if (!(Table[dest.row][dest.col] & INACTIVE))
    {
      if ((dest.row == end.row) && (dest.col == end.col)) return 1;
      
      if (*update)
      {
        // add
        branches[total].row = dest.row;
        branches[total].col = dest.col;
        
        ++total;
      }
      else
      {
        // replace
        branches[b].row = dest.row;
        branches[b].col = dest.col;
        
        *update = 1;
      }

      Table[dest.row][dest.col] |= INACTIVE;      
    }
  }
  return 0;
}

int GetSteps()
{
    int steps = 0;
    struct POINT s;
    char moved;
    int k, tmp, i;
        
    for ( ; total ; ++steps)
    {	
      tmp = total;
      
      for ( k = 0 ; k < tmp; )
      {     
        moved = 0;
          
        s.row = branches[k].row;s.col = branches[k].col;
          
        if (MakeMove(&s, k, MOVE_UP, &moved)) return steps+1;		
        if (MakeMove(&s, k, MOVE_DOWN, &moved)) return steps+1;		
        if (MakeMove(&s, k, MOVE_LEFT, &moved)) return steps+1;		
        if (MakeMove(&s, k, MOVE_RIGHT, &moved)) return steps+1;
          
        if (!moved)
        {
          if (--total)
          {
            for ( i = k ; i < total ; i++)
            {
              branches[i].row = branches[i+1].row;
              branches[i].col = branches[i+1].col;              
            }
            --tmp;
          }
          else return 0;
        }
        else ++k;
      }        
    }	
    return 0;
}	

int main(int argc, char** argv)
{
    FILE *fin = fopen(FILENAME,"r");

    int r, c, rows, columns;

    if (!fin) return 0; 

    fscanf(fin,"%i %i",&rows,&columns);

    if (!(rows && columns))
    {
        fclose(fin);
return 0;
    }

    Table = (char**)malloc(sizeof(char*)*rows);

    for (r = 0; r < rows; r++)
    {
        Table[r] = (char*)malloc(sizeof(char)*columns);

        for (c = 0; c < columns; c++) 
          fscanf(fin,"%uh",&Table[r][c]);    		
    }

    branches = (struct POINT*)malloc(sizeof(struct POINT)*BRANCH_MAX);

    fscanf(fin,"%d %d", &branches[0].row, &branches[0].col);
    fscanf(fin,"%d %d", &end.row, &end.col);
    fclose(fin);

    --branches[0].row;
    --branches[0].col;
    --end.row; 
    --end.col;
    
    total = 1;

    Table[branches[0].row][branches[0].col] |= INACTIVE;

    printf("%d\r\n",GetSteps());

    free(branches);

    for (r = 0; r < rows; r++)
      free(Table[r]);

    free(Table);	

    return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma solução em Java, usando o BFS (Breadth First Search). Acho que funciona...

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class LabirintoDigital {

  static Square[][] lab;
  static int w;
  static int h;
  static Queue<Coord> q;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    w = sc.nextInt();
    h = sc.nextInt();
    lab = new Square[h][w];
    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) {
        lab[y][x] = new Square(sc.nextInt());
      }
    }
    Coord init = new Coord(sc.nextInt()-1, sc.nextInt()-1);
    Coord fin = new Coord(sc.nextInt()-1, sc.nextInt()-1);
    q = new LinkedList<Coord>();
    q.add(init);
    lab[init.x][init.y].distance = 0;
    int x;
    int y;
    while(!lab[fin.x][fin.y].visited) {
      Coord next = q.poll();
      x = next.x;
      y = next.y;
      lab[y][x].visited = true;
      if (x+1 < w && !lab[y][x+1].visited && !lab[y][x+1].left_wall) {
        q.add(new Coord(x+1,y));
        lab[y][x+1].distance = lab[y][x].distance+1;
      }
      if (x-1 >= 0 && !lab[y][x-1].visited && !lab[y][x-1].right_wall) {
        q.add(new Coord(x-1,y));
        lab[y][x-1].distance = lab[y][x].distance+1;
      }
      if (y+1 < h && !lab[y+1][x].visited && !lab[y+1][x].up_wall) {
        q.add(new Coord(x,y+1));
        lab[y+1][x].distance = lab[y][x].distance+1;
      }
      if (y-1 >= 0 && !lab[y-1][x].visited && !lab[y-1][x].down_wall) {
        q.add(new Coord(x,y-1));
        lab[y-1][x].distance = lab[y][x].distance+1;
      }
    }
    System.out.println(lab[fin.x][fin.y].distance);
  }
  
  private static class Coord {
    private int x;
    private int y;
    
    private Coord(int x, int y) {
      this.x = x;
      this.y = y;
    }
    
    public String toString() {
      return x + " " + y;
    }
  }
  
  private static class Square {
    private boolean left_wall;
    private boolean up_wall;
    private boolean right_wall;
    private boolean down_wall;
    private boolean visited;
    private int distance;
    
    private Square(int walls) {
      left_wall  = (walls & 1) == 1;
      up_wall    = (walls & 2) == 2;
      right_wall = (walls & 4) == 4;
      down_wall  = (walls & 8) == 8;
      visited = false;
      distance = Integer.MAX_VALUE;
    }
    
    public String toString() {
      return visited + " " + distance;
    }
  }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui fica em Haskell

import Data.List (concatMap)
import Data.Bits (testBit)
import Control.Arrow ((&&&))
import Data.Graph.Inductive
import Data.Graph.Inductive.Graph (mkUGraph)
import Data.Graph.Inductive.Query.BFS (esp)

main = getContents >>= print . proc . map (words) . lines

proc (tam:fs) = pred $ length $ esp start end $ (mkUGraph nodos edges :: Gr () ())
   where
   [x', y'] = map read tam
   [sx, sy, ex, ey] = map read $ concat $ drop y' fs
   start = sy + (sx - 1) * y'
   end = ey + (ex - 1) * y'
   nodos = [1..x'*y']
   lab = concatMap (map read) (take y' fs) :: [int]
   edges = concatMap mkEdge $ zip [1..] lab
   mkEdge (i,v) = map (($i).fst) $ livres $ zip waysFuns $ map (testBit v) [0..3]
   livres = filter (not.snd)
   waysFuns = [oeste, norte, este, sul]
   oeste, norte, este, sul :: Int -> (Int, Int)
   oeste = id &&& (#1)
   norte = id &&& (#x')
   este = id &&& (+1)
   sul = id &&& (+x')
   (#) = (-)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora