C++, Gomoku

**defender19** · 13/01/2012, 17h33

Bonsoir!

Cherchant à réaliser un exo sur le Gomoku, sujet :

Cliquez pour afficher

J'ai fait ça :

Code:

#include <iostream>

using namespace std;



int main(){
    int nb;
    cin>>nb;
    if(nb<1 && nb>40)
        return 0;

    int tab[nb][nb];
    for(int i=0; i<nb; i++)
        for(int j=0; j<nb; j++)
            cin>>tab[i][j];

    
    for(int i=0; i<nb; i++)
        for(int j=0; j<nb; j++)
            if(tab[i][j]!=0){
                int eq=tab[i][j];
                int cpt=0;

                // horizontal
                for(int a=j; a<j+5 && a+1<nb; a++)
                    if(tab[i][a+1]!=eq)
                            cpt++;
                if(cpt==0){
                    cout<<eq;
                    return 0;
                }
                cpt=0;

                for(int a=i;a<i+5 && a+1<nb; a++) // vertical
                        if(tab[a+1][j]!=eq)
                            cpt++;

                if(cpt==0){
                    cout<<eq;
                    return 0;
                }

                cpt=0;
                for(int a=i,b=j; a<i+5 && a+1<nb && b<j+5 && b+1<nb; a++,b++)
                    if(tab[a+1][b+1]!=eq)
                            cpt++;

                if(cpt==0){
                    cout<<eq;
                    return 0;
                }
                cpt=0;

                for(int a=i, b=j; a<i+5 && a+1<nb && b>j-5 && b-1>=0; i++,j--)
                    if(tab[a+1][b-1]!=eq)
                            cpt++;

                if(cpt==0){
                    cout<<eq;
                    return 0;
                }
            }

    cout<<"0";
    return 0;
}

Ca marche parfois, mais dans l'exemple du sujet, ça me sort 2... Je sais pas pourquoi. Parfois, ça me met Programme trop long, ça c'est le coup de toute les boucles, j'imagine... Si vous avez une idée, merci!

invite4492c379 · 13/01/2012, 19h27

Hello,

je n'ai pas fouillé ton code, je l'ai juste copié/collé, compilé et exécuté avec le jeu de test. Il met 18s sur ma machine pour me sortir 6.

Une technique que tu peux utiliser :

Pour

Code:

0 0 2 0 1 0
0 1 2 2 2 1
0 0 2 0 1 0
0 0 2 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0

tu crées

Code:

0 0 0 0 0 0 | 0 0 0 0
0 0 0 0 0 0 | 0 0 0 0
0 0 0 0 0 0 | 0 0 0 0
0 0 0 0 0 0 | 0 0 0 0
---------------------
0 0 2 0 1 0 | 0 0 0 0
0 1 2 2 2 1 | 0 0 0 0
0 0 2 0 1 0 | 0 0 0 0
0 0 2 1 0 0 | 0 0 0 0
0 0 1 0 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
0 0 0 0 0 0 | 0 0 0 0
0 0 0 0 0 0 | 0 0 0 0
0 0 0 0 0 0 | 0 0 0 0

Tu n'as besoin que de checker les directions NE E SE S pour toutes les cases du tableau original.
Une fonction avec NE = deplacement (-1,1), E=(0,1), SE=(1,1) et S=(1,0)

**piwi** · 13/01/2012, 20h06

Bonsoir,

Quand tu as un code comme ça, c'est toujours sympa d'y mettre des commentaires. Parce qu'aller regarder là dedans, ça file la migraine.
Dans le même ordre d'idée, c'est sympa de mettre un peu de texte à afficher durant le déroulement du programme, histoire que l'utilisateur sache un peu ce qui se passe et ce qu'il fait (exemple: entrer la variable N: ). Moi, j'aime bien mettre un texte dans les boucles qui affiche à l'écran les itérations, on voit tout de suite si il y a un couac (phrase type "itération n". Si j'attends que la boucle s'exécute 3 fois, je vois si c'est le cas ou pas).

piwi

**defender19** · 13/01/2012, 21h52

Merci pour vos réponses!

Alors pour Piwi, j'ai pas mis de commentaires, c'est vrai j'en mais assez rarement, mais sinon pour le coup des "entrez la variable,...", je l'ai pas mis, parce qu'en fait c'est un exercice sur un site d'algo, et il faut afficher uniquement à l'écran ce qu'ils veulent, sinon je le fais

Pareil pour les itérations, pour tester ou ça pèche, je le fais!

Par contre, Photon, j'ai pas tout pigé le coup des 5 carrés en plus... Je suis parti du principe qu'on parcourt le tableau de gauche à droite et de haut en bas, donc pour tester en horizontal, je ne teste que vers la droite, pareil pour la verticale, je teste que vers le bas à chaque fois...

A voir en vidéo sur Futura · Aujourd'hui

invite4492c379 · 13/01/2012, 22h42

Envoyé par defender19

Merci pour vos réponses!

Alors pour Piwi, j'ai pas mis de commentaires, c'est vrai j'en mais assez rarement, mais sinon pour le coup des "entrez la variable,...", je l'ai pas mis, parce qu'en fait c'est un exercice sur un site d'algo, et il faut afficher uniquement à l'écran ce qu'ils veulent, sinon je le fais

Pareil pour les itérations, pour tester ou ça pèche, je le fais!

Par contre, Photon, j'ai pas tout pigé le coup des 5 carrés en plus... Je suis parti du principe qu'on parcourt le tableau de gauche à droite et de haut en bas, donc pour tester en horizontal, je ne teste que vers la droite, pareil pour la verticale, je teste que vers le bas à chaque fois...

J'ai tapé large, on peut réduire les 0 ajoutés. Le fait d'ajouter les 0 simplifie la logique de recherche car tu n'as plus besoin de vérifier si tu ne débordes pas du tableau.

Ton code est «pourri», ne le prend pas mal surtout, ça arrive à tout le monde. Il est illisible et incompréhensible en première lecture. Écris des fonctions. Ça facilite la lecture et le debuggage.

Ton code est atrocement lent pour un tableau 6x6 ...

je regarde ça de plus prêt et je te donnerai une version de ce qui peut être fait.

invite4492c379 · 14/01/2012, 00h53

Re-.

J'ai rapidement écrit un petit truc, sans commentaires (pas trop envie) mais qui me semble assez lisible. Un source en C, allocation dynamique, libération mémoire OK.
Tout est dans le zip :

Code:

Archive:  gomoku.zip
  Length      Date    Time    Name
---------  ---------- -----   ----
     2638  2012-01-14 01:27   gomoku.c
      203  2012-01-14 01:31   gomoku_Hor.in
       74  2012-01-13 23:58   gomoku.in
     3243  2012-01-14 01:36   gomoku_Max_Empty.in
     3243  2012-01-14 01:36   gomoku_Max_HG-E.in
     3243  2012-01-14 01:37   gomoku_Max_HG-SE.in
     3243  2012-01-14 01:37   gomoku_Max_HG-S.in
     3243  2012-01-14 01:35   gomoku_Max.in
      203  2012-01-14 01:32   gomoku_NE.in
      203  2012-01-14 01:32   gomoku_SE.in
      203  2012-01-14 01:29   gomoku_Vert.in
---------                     -------
    19739                     11 files

En mode debug pour avoir des infos supplémentaires tu compiles avec

Code:

gcc -g -Wall -Wextra -DDEBUG -o gomoku gomoku.c

En mode réel :

Code:

gcc -Wall -Wextra -o gomoku gomoku.c

Je t'ai joint plusieurs fichiers de test ... je ne les ai pas tous créés ... tu testes avec :

Code:

./gomoku < gomoku_Max_HG-E.in

L'idée pour les tests est d'avoir au moins trois tailles N=1, N=40, N=6 par exemple
Pour chaque taille tu testes une victoire dans chaque coin et dans chaque direction, au centre sans toucher les bords chaque direction, au centre en touchant les bords dans chaque direction, sans aucune victoire, un tableau aléatoire. (l'idéal est de faire un script ...).
Avec ça tu blindes.

gomoku.zip

**defender19** · 14/01/2012, 17h18

Merci bien! Un peu occupé ce week end, je regarde ça lundi et je te demande au cas ou si j'ai des questions!

En tout cas, ton code passe haut la main les tests, avec 9test à 0s et 1 à 0.004 s!

Merci bien

invite4492c379 · 14/01/2012, 17h22

Envoyé par defender19

Merci bien! Un peu occupé ce week end, je regarde ça lundi et je te demande au cas ou si j'ai des questions!

En tout cas, ton code passe haut la main les tests, avec 9test à 0s et 1 à 0.004 s!

Merci bien

De rien

Il est un peu brut de fonderie ... et largement améliorable. Juste pour dire que ce n'est pas parce qu'un code est long ou utilise des sdd un peu élaborées que pour autant il sera long à exécuter (tu peux gagner quelques microsecondes en skippant la libération de la mémoire ...).

**defender19** · 14/01/2012, 17h53

C'est sur, mais après la c'est des exos de base d'algo, et je me sens pas écrire ce que tu as fait

Je regarderai en détail, parcequ'au premier abord, je pige pas tout!

C++, Gomoku

C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku

Re : C++, Gomoku