CodinGame retrouver motif dans une image

Version imprimable

08/01/2020, 10h18
ilmatic

CodinGame retrouver motif dans une image

Bonjour à tous j'ai effectué aujourd'hui un condingame C#. Je suis tombé sur un exercice ou je n'ai pas vraiment compris l'énoncé. Si quelqu'un peut m'aiguiller svp je vous mets l'énoncé ci-dessous. Merci de vos réponses.

Objectif

Trouver un motif dans une image.

Règles

On vous donne 2 images : une image de base, et un motif qui peut être présent dans cette image.

Chaque image est représentée sous la forme d'[[anArray]] de chaînes de caractères, où chaque élément représente une ligne de pixels de l'image, et chaque caractère représente un pixel. Il n'est pas nécessaire de comprendre en détail cet encodage pour résoudre ce problème, mais pour information, des explications sont fournies plus bas.

Vous devez retourner la position x, y de ce motif dans l'image, ou [-1, -1] si le motif n'est pas présent dans l'image. Si le motif apparaît plusieurs fois dans l'image, retournez la position du plus haut (le y le plus petit), et en cas d'égalité, le plus à gauche (le x le plus petit).

La position du motif est déterminée par les coordonnées x, y de son coin en haut à gauche. x représente la colonne, y représente la ligne, et les coordonnées [0, 0] représentent le coin en haut à gauche.

Implémentation

Implément la [[functionLabel]] [[functionSimple]] où les paramètres sont :

imageWidth: la largeur de l'image
imageHeight: la hauteur de l'image
image: l'image, [[anArray]] de strings, où chaque caractère représente un pixel
patternWidth: la largeur du motif
patternHeight: la hauteur du motif
pattern: le motif, [[anArray]] de strings, où chaque caractère représente un pixel
et qui doit retourner :

si le motif est présent dans l'image : la position x, y, sous la forme d'[[anArray]] de 2 entiers, représentant le coin en haut à gauche du 1er motif, en partant du haut vers le bas, et de gauche à droite.
si le motif n'est pas présent dans l'image : [-1, -1]

Conditions de Victoire

Le motif est effectivement situé aux coordonnées x, y.
Si le motif apparaît plusieurs fois dans l'image, retournez la position du plus haut (le y le plus petit), et en cas d'égalité, le plus à gauche (le x le plus petit).

Conditions de Défaite

La sous-image qui commence aux coordonnées x, y ne correspond pas au motif.
Vous prenez plus d'une seconde à répondre.
Il y a un autre motif qui correspond, plus haut ou plus à gauche que le votre.
Contraintes

1 ≤ imageWidth ≤ 400

1 ≤ imageHeight ≤ 400

1 ≤ patternWidth ≤ 400

1 ≤ patternHeight ≤ 400

Temps de réponse ≤ 1s

Détails sur l'encodage

Initialement, une image est un tableau d'entiers à 2 dimensions, où chaque entier représente un pixel (en utilisant la notation RGB). Toutes nos images possèdent au maximum 62 couleurs différentes, de manière à ce que nous puissions encoder chaque entier en un caractère parmi 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ. Nous avons simplement transformé l'image en un tableau de strings, où la 1ère string est la 1ère ligne de l'image, etc.

Par exemple, cette image 3x3 :

est représentée en tableau d'entiers à 2 dimensions comme :

[

[0xff0000, 0x00ff00, 0x0000ff],

[0xd3d3d3, 0x000000, 0xd3d3d3],

[0xff0000, 0x00ff00, 0x0000ff]

]

qui est ensuité encodée en un tableau de strings en :

[

"012",

"343",

"012"

]
09/01/2020, 14h27
lead8209

Salut, c'est quoi la question ?
10/04/2021, 22h03
serpentcorail

Salut j'ai eu la même en php et je me suis planté car j'ai paniqué il faut parcourir le tableau de caractère avec deuc bouvle for mais je me suis trompé dans l'ordre des boucle alors çà ne marchais pas et je me suis crispé dés que le test fu fini j'ai vu l'érreur

En algo, c'est 1 truc comme cela :mrgreen: (il me semble que je l'ai eu en C/ C++)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
array result[2];
 
if ((patternWidth  >= 1) && (patternWidth  <= 400) &&
    (patternHeight >= 1) && (patternHeight <= 400) &&
    (imageWidth    >= 1) && (imageWidth    <= 400) &&
    (imageHeight   >= 1) && (imageHeight   <= 400) &&
    (patternWidth <= imageWidth) && (patternHeight <= imageHeight)) {
 
    int img_x, img_y, pattern_x, pattern_y;
    bool pattern_not_found, pattern_is_matching;
 
    result = [-1, -1];
    pattern_not_found = true;
 
    for(img_x=0; (pattern_not_found  && (img_x <= (imageWidth - patternWidth))); ++img_x) { // <- check if img_x == (imageWidth - patternWidth) or not
        for(img_y=0; (pattern_not_found  && (img_y <= (imageHeight - patternHeight))); ++img_y) { // <- check if img_y == (imageHeight - patternHeight) or not
            pattern_is_matching = true
 
            for(pattern_x=0; (pattern_is_matching && (pattern_x < patternWidth)); ++pattern_x) {
                for(pattern_y=0; (pattern_is_matching && (pattern_y < patternHeight)); ++pattern_y) {
                    if (img[(img_x + pattern_x), (img_y + pattern_y)] != pattern[pattern_x, pattern_y]) {
                        pattern_is_matching = false
                    }
                }
            }
 
            if (pattern_is_matching) {
                pattern_not_found = false;
                result = [img_x, img_y];
            }
        }
    }
} else {
//  XXX Error : preconditions
//  result = ???
}
 
return result;

en PHP

version php

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function solve(
    $imageWidth,
    $imageHeight,
    array $image,
    $patternWidth,
    $patternHeight,
    array $pattern
) {
 
    $result = [-1, -1];
 
    if (($patternWidth  >= 1) && ($patternWidth  <= 400) &&
        ($patternHeight >= 1) && ($patternHeight <= 400) &&
        ($imageWidth    >= 1) && ($imageWidth    <= 400) &&
        ($imageHeight   >= 1) && ($imageHeight   <= 400) &&
        ($patternWidth <= $imageWidth) && ($patternHeight <= $imageHeight)) {
 
        $img_x; $img_y; $pattern_x; $pattern_y; $pattern_not_found; $pattern_is_matching;
        $pattern_not_found = true;
 
        for($img_x=0; ($pattern_not_found  && ($img_x <= ($imageWidth - $patternWidth))); $img_x++) { // <- check if img_x == (imageWidth - $patternWidth) or not
            for($img_y=0; ($pattern_not_found  && ($img_y <= ($imageHeight - $patternHeight))); $img_y++) { // <- check if img_y == ($imageHeight - $patternHeight) or not
                $pattern_is_matching = true;
 
                for($pattern_x=0; ($pattern_is_matching && ($pattern_x < $patternWidth)); ++$pattern_x) {
                    for($pattern_y=0; ($pattern_is_matching && ($pattern_y < $patternHeight)); ++$pattern_y) {
                        if ($image[$img_x + $pattern_x][$img_y + $pattern_y] != $pattern[$pattern_x][$pattern_y]) {
                            $pattern_is_matching = false;
                        }
                    }
                }
 
                if ($pattern_is_matching) {
                    $pattern_not_found = false;
                    $result = [$img_x, $img_y];
                }
            }
        }
    }
 
    return $result;
 
 
 }
 
 $image = [
 [0xff0000, 0x00ff00, 0x0000ff],
 [0xd3d3d3, 0x000000, 0xd3d3d3],
 [0xff0000, 0x00ff00, 0x0000d3],
 [0xff0000, 0x00ff00, 0x0000ff],
 [0xff0000, 0x00ff00, 0x0000ff],
 [0xff0000, 0x00ff00, 0x0000ff]
 ];
 $pattern = [
 [0xff0000, 0x00ff00, 0x0000ff],
 [0xff0000, 0x00ff00, 0x0000ff],
 [0xff0000, 0x00ff00, 0x0000ff]
 ];
 
 print_r($image);
 
 $result = solve(6, 3, $image, 3, 3, $pattern);
 
 
 print_r($result);

24/04/2022, 00h37
aba2s

Le même exercice sur python

Je suis tombé sur le même exercice en Python. Je n'ai même pas compris l'énoncé. Pourriez - vous svp m'aider ?