Ir para o conteúdo
DFPA46

Resolver Nonograms

Mensagens Recomendadas

DFPA46

Boas,

tenho um projecto em mãos que consiste em resolver um nonogram 20x20 (para quem não sabe pode encontrar aqui informação e jogar tbm ;) : http://pt.puzzle-nonograms.com/) a partir de um ficheiro .txt de entrada com o seguinte formato:

//dimensão da grelha

20

20

//entradas das linhas (o primeiro destes números corresponde à dimensão do vector de inteiros da

primeira linha do puzzle; os restantes números da sequência formam o vector.)

1 2

1 2

3 4 2 2

5 4 1 1 1 1

4 2 1 3 1

3 2 1 7

4 1 3 3 2

2 10 1

5 8 2 1 1 1

3 8 1 1

4 9 1 1 1

4 3 8 1 1

2 2 12

4 3 2 4 3

4 2 2 4 3

3 3 4 2

2 3 2

3 2 1 2

2 5 4

2 4 2

1 6

//entradas das colunas (o primeiro destes números corresponde à dimensão do vector de inteiros da

primeira coluna do puzzle; os restantes números da sequência formam o vector.)

1 9

2 9 3

4 4 4 1 1

3 1 2 8

3 4 9 1

4 2 7 1 1

2 7 1

3 1 5 1

3 8 5 1

4 1 3 7 1

5 1 2 2 3 1

5 2 1 2 2 1

3 2 4 1

4 2 1 4 1

6 1 1 1 1 2 1

4 1 2 1 2

3 8 1 2

1 4

1 2

Posto isto, não sei que estrutura de dados usar para guardar e manipular os dados, que seja, preferencialmente, fácil de programar, que não exija memória em excesso e que não influencie o tempo de execução em grande escala.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
DFPA46

e isso não e ineficeinte e nao tem um tempo de execução enorme? e que num 20x20 temos inúmeras possibilidades...

Editado por DFPA46

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
DFPA46

e que algoritmo mais eficiente é que posso usar? e que tem de ser o mais eficiente possivel, e o brute force embora seja tentador de se usar é ineficiente..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

existe alguma razão para que a eficiência seja para ter em conta ?

faz primeiro pro brute force e depois pensa em passos para simplificar o processo ...


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

então aprende que não só a aprendizagem mas como o desenvolvimento em geral é um processo iterativo

- primeira iteração : brute force


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jimbrix12345

Estou a fazer algo semelhante...

Chegou agora a parte de guardar todas as possibilidades de uma linha num array. O problema é que nao faço ideia do nº que vai ter (depende de linha para linha, puzzle, nº peças, etc)).

Como posso fazer isso?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Estou a fazer algo semelhante...

Chegou agora a parte de guardar todas as possibilidades de uma linha num array. O problema é que nao faço ideia do nº que vai ter (depende de linha para linha, puzzle, nº peças, etc)).

Como posso fazer isso?

um problema correcto só tem uma solução


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jimbrix12345

Não é isso que quero dizer.

Quero parte de guardar todas as possibilidades de uma linha. Guardo onde? Além disso eu não sei o tamanho que vai ter.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Quero parte de guardar todas as possibilidades de uma linha.

sum solução = uma possibilidade

Guardo onde? Além disso eu não sei o tamanho que vai ter.

o tamanho está definido no problema


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação 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

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.