C++, Gomoku

[invite2216f80a]

Bonsoir!

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

 Cliquez pour afficher

Le Gomoku est un jeu de plateau à deux joueurs, dans lequel pour gagner, chaque joueur doit réussir à aligner 5 pions sur des cases consécutives d'un plateau, horizontalement, verticalement ou en diagonale. Le plateau est une grille carrée, de dimension quelconque.

Ecrivez un programme qui lit en entrée le contenu d'une partie de Gomoku, et détermine si l'un des joueurs a gagné.
LIMITES DE TEMPS ET DE MEMOIRE
Temps : 1s sur une machine à 1Ghz.
Mémoire : 1000 Ko.
CONTRAINTES
1 <= N <= 40, où N est le nombre de lignes/colonnes du plateau utilisé pour la partie.
ENTRÉE
La première ligne de l'entrée contient un entier N : le nombre de colonnes et de lignes du plateau de Gomoku.

Chacune des N lignes suivantes contient N entiers, séparés par des espaces, correspondant au contenu des cases d'une ligne du plateau. L'entier vaut 0 si la case est vide, 1 si elle contient un pion du joueur 1, et 2 pour un pion du joueur 2.
SORTIE
Votre programme doit afficher une ligne contenant un entier : le numéro du joueur gagnant (1 ou 2), ou 0 si aucun des joueurs n'a aligné 5 pions.

EXEMPLE

entrée :
6
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

sortie :
1

J'ai fait ça :

#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]

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

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

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]

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

[invite2216f80a]

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]

[invite4492c379]

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]

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 :

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

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

En mode réel :

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 :

./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

[invite2216f80a]

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]

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 ...).

[invite2216f80a]

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!