localização de sub-matrizes

[polska]

Boas pessoal, preciso de uma ajuda, eu estou a tentar localizar 5 formas numa matriz de 0's e 1's, as formas são formadas por 1 e os limites das formas tem de ser 0, ou seja, uma forma que contenha pegado um 1 que não faça parte dessa forma, não conta..

Bem, para isto, eu fiz 5 matrizes 5x5 onde desenhei as formas e coloquei nos limites que é preciso os 0's :

char g1[5][5],g2[5][5],g3[5][5],g4[5][5],g5[5][5];
void inicializaGambozinos(){
//GAMBOZINO 1
g1[0][2]='0';
g1[1][1]='0';g1[1][2]='1';g1[1][3]='0';
g1[2][0]='0';g1[2][1]='0';g1[2][2]='1';g1[2][3]='1';g1[2][4]='0';
g1[3][0]='0';g1[3][1]='1';g1[3][2]='1';g1[3][3]='0';
g1[4][1]='0';g1[4][2]='0';
//GAMBOZINO 2
g2[0][2]='0';
g2[1][1]='0';g2[1][2]='1';g2[1][3]='0';
g2[2][0]='0';g2[2][1]='1';g2[2][2]='1';g2[2][3]='0';
g2[3][1]='0';g2[3][2]='1';g2[3][3]='1';g2[3][4]='0';
g2[4][2]='0';g2[4][3]='0';
//GAMBOZINO 3
g3[0][1]='0';g3[0][2]='0';
g3[1][0]='0';g3[1][1]='1';g3[1][2]='1';g3[1][3]='0';
g3[2][1]='0';g3[2][2]='1';g3[2][3]='1';g3[2][4]='0';
g3[3][1]='0';g3[3][2]='1';g3[3][3]='0';
g3[4][2]='0';
//GAMBOZINO 4
g4[0][3]='0';
g4[1][2]='0';g4[1][3]='1';g4[1][4]='0';
g4[2][0]='0';g4[2][1]='1';g4[2][2]='1';g4[2][3]='1';g4[2][4]='0';
g4[3][1]='0';g4[3][2]='1';g4[3][3]='0';
g4[4][2]='0';
//GAMBOZINO 5
g5[0][2]='0';
g5[1][1]='0';g5[1][2]='1';g5[1][3]='0';
g5[2][0]='0';g5[2][1]='1';g5[2][2]='1';g5[2][3]='1';g5[2][4]='0';
g5[3][0]='0';g5[3][1]='1';g5[3][2]='0';
g5[4][1]='0';
}

As formas são assim:

http://imageshack.us...8077924768.png/

Como podem ser formadas (limites etc...)

http://imageshack.us...8077924768.png/

Agora, preciso de localizar numa matriz quantas formas existemp, por exemplo, deste tipo:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 0 0 1 0 1 0 0 0 0 1 0

0 1 0 1 1 1 1 0 1 1 0 0 1 0 0

0 1 0 0 0 0 1 1 1 0 0 1 1 1 0

0 0 0 1 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

o resultado é 1 ...

Bem, eu precisava de ajuda, como é que eu consigo verificar se alguma matriz das formas 5x5 se localiza nesta matriz grande? Estou um bocado confuso, pois nas bordas nunca existem formas, logo a primeira e ultima linha assim como primeira e ultima coluna não preciso de verificar se existe...

Alguém me conssegue ajudar?

ps: esta pareceu-me a forma mais eficaz de resolver este problema, mas se alguém tiver outra idea, agradeço ;D

Edited June 14, 2012 at 11:28 PM by polska

[HappyHippyHippo]

eu faria assim :

1 matrix para a forma (3x3, visto que 5x5 não há necessidade)

1 matrix do quadro a verificar (nxm)

1 enumeração das diferentes posições da peça (4 direções x 2 espelhadas)

funções de verificação da matrix no quadro com estes argumentos (isto dentro da classe quadro)

protected:
int find(matrix peca, enum direcao, int x, y) {
 // verificar se a peca na direcao d se encontra na posicao (x,y)
}

int find(matrix peca, enum direcao) {
 // ciclo que pesquisa a peca em todo o tabuleiro
 // nota : chamada da funções anterior
}

public:
int find(matrix peca) {
 // ciclo de pesquisa da peca em todo o o tabuleiro para as diferentes direções
 // nota : chamada da funções anterior
}

agora, claro que terás de verificar que não existem blocos adjacentes à peça na função de verificação (somente na vertical e horizontal porque na diagonal não conta)

se for caso disso, podes ainda sub-dividir o trabalho de pesquisa da peca por direcoes :

+ 8 funções protegidas para pesquisar o peca na direcção D na posição (X, Y) no tabuleiro

Edited June 14, 2012 at 11:47 PM by HappyHippyHippo

[polska]

eu faria assim :

1 matrix para a forma (3x3, visto que 5x5 não há necessidade)

1 matrix do quadro a verificar (nxm)

1 enumeração das diferentes posições da peça (4 direções x 2 espelhadas)

funções de verificação da matrix no quadro com estes argumentos (isto dentro da classe quadro)

protected:
int find(matrix peca, enum direcao, int x, y) {
 // verificar se a peca na direcao d se encontra na posicao (x,y)
}

int find(matrix peca, enum direcao) {
 // ciclo que pesquisa a peca em todo o tabuleiro
 // nota : chamada da funções anterior
}

public:
int find(matrix peca) {
 // ciclo de pesquisa da peca em todo o o tabuleiro para as diferentes direções
 // nota : chamada da funções anterior
}

agora, claro que terás de verificar que não existem blocos adjacentes à peça na função de verificação (somente na vertical e horizontal porque na diagonal não conta)

se for caso disso, podes ainda sub-dividir o trabalho de pesquisa da peca por direcoes :

+ 8 funções protegidas para pesquisar o peca na direcção D na posição (X, Y) no tabuleiro

Sinceramente, essa é uma solução bastante complexa para a minha cabeça 😛 , ainda não sei trabalhar com classes, eu procurava algo que eu conseguisse fazer com 2 ou 3 for no máximo ;D , eu costumo chegar sempre lá mas este tornou-se bastante confuso..

[HappyHippyHippo]

então fizeste post na secção de c++ e estás a dizer que não sabes trabalhar com classes ??

para isso fazias na secção de c !!!

no entanto podes sempre resolver da mesma forma, basta implementar as funções todas com nomes diferentes e chamares a correcta

[pikax]

ainda não sei trabalhar com classes

pensa assim: Classes sao como estruturas em C(tirando heranca, etc), so' que classes podem ter metodos(funcoes). Ja' agora estruturas em C++ e' praticamente classes so' que todos os membros e metodos sao publicos.

[HappyHippyHippo]

so' que classes podem ter metodos(funcoes).

bem ... já ques estamos na área de c++, experimenta isto

#include <stdio.h>
#include <stdlib.h>

struct Test {
 int i;
 Test(int a) { i = a; };
 int inc() { i++; return i; }
};

int main(void) {
 struct Test t(4);
 printf("Test %d\n", t.inc());
 return 0;
}

[polska]

então fizeste post na secção de c++ e estás a dizer que não sabes trabalhar com classes ??

para isso fazias na secção de c !!!

no entanto podes sempre resolver da mesma forma, basta implementar as funções todas com nomes diferentes e chamares a correcta

Eu pus na de c++ porque estou a usar métodos de c++ e a aprender esta linguagem, mas ainda não cheguei a orientação a objectos...

já agora, o que queres com isto: 1 enumeração das diferentes posições da peça (4 direções x 2 espelhadas)

Eu não sei se estou a pensar corretamente, mas tu queres tipo testar as 4 posições diferentes de cada peça? Se assim for, não é necessário, porque as peças só aparecem nesta posição:

http://imageshack.us...8077924768.png/

pensa assim: Classes sao como estruturas em C(tirando heranca, etc), so' que classes podem ter metodos(funcoes). Ja' agora estruturas em C++ e' praticamente classes so' que todos os membros e metodos sao publicos.

Eu já tinha lido algo parecido no livro que estou a estudar, mas estou a seguir tudo direitinho e ainda não cheguei ai... 👍

Edited June 16, 2012 at 02:51 PM by polska