Shadows of the knight Ep.1

Page web ISIMA
Fichier.org source
Défi de programmation - Shadows of the knight Ep.1

1. Introduction

Dans ce problème, nous contrôlons un batman, qui se trouve dans un immeuble. On peut le faire se déplacer de fenêtre en fenêtre, il y a une bombe sur une fenêtre à trouver. A chaque fois que l’on déplace le Batman, on nous donne une information si la bombe se trouve au dessus, à droite, au dessus à droite, etc. du Batman.
Le but est de trouver la bombe en le moins de déplacements possible.

2. Approche utilisée

2.1. Description synoptique

J’ai utilisé une approche dichotomique pour résoudre ce problème.
On possède un intervalle de base : l’immeuble entier.
A chaque tour on se place au centre de cet intervalle, et on le réduit en fonction de l’information qui nous est donnée (ex : si on nous dit que la bombe est à notre gauche, on coupe la moitié droite de l’intervalle).
On répète jusqu’à ce que l’intervalle n’ait la taille que d’une fenêtre, donc la fenêtre où la bombe est posée.
Cet algorithme est de complexité logarithmique.

2.2. Algorithme

left = 0
right = largeur de l’immeuble - 1
top = 0
bottom = hauteur de l’immeuble - 1
x, y : position intiale du Batman

Boucle principale :

dir = entrée utilisateur, la direction de la bombe (en utilisant les charactères U, D, L, R)

Mise à jour de l’intervalle en fonction de la direction :
Si dir contient le charactère ’U’ :
- bottom = y - 1
Sinon si dir contient le charactère ’D’ :
- top = y + 1
Si dir contient le charactère ’L’ :
- right = x - 1
Sinon si dir contient le charactère ’R’ :
- left = x + 1
x = moyenne de left et right
y = moyenne de top et bottom
Afficher x et y

Fin boucle
(Condigame arrête la boucle quand la bonne position a été trouvée ou si le temps de test est dépassé.

3. Résolution

#include <stdio.h>
#include <string.h>

// Fonction outils renvoyant 1 si le string donné contient le charactère passé en paramètre
int contain(char str[], char chr) {
    return strchr(str, chr) != NULL;
}

int main()
{
    // width, height of the building.
    int W, H;
    scanf("%d%d", &W, &H);
    int left = 0, right = W - 1;
    int top = 0, bottom = H - 1;
    int N;
    scanf("%d", &N);
    int X;
    int Y;
    scanf("%d%d", &X, &Y);

    while (1) {
        char dir[4];
        scanf("%s", dir);

        // Axe Y (Up and Down)
        if (contain(dir, 'U')) {
            bottom = Y-1;
        } else if (contain(dir, 'D')) {
            top = Y+1;
        }

        // Axe X (Left and Right)
        if (contain(dir, 'L')) {
            right = X-1;
        } else if (contain(dir, 'R')) {
            left = X+1;
        }

        X = (left + right) / 2;
        Y = (top + bottom) / 2;

        printf("%d %d\n", X, Y);
    }

    return 0;
}

4. Comparaison avec une autre solution

A partir de cette solution externe :

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

int main()
{
    int w, h, t, px, py, x, y;
    scanf("%d %d %d %d %d", &w, &h, &t, &px, &py);
    x = y = 0;

    while ( 1 )
    {
        int ax = px - x + 1;
        int aw = px - w;
        int ay = py - y + 1;
        int ah = py - h;

        char* dir = (char [4]){};
        scanf("%s", dir);

        for ( ; *dir != '\0'; dir++ )
        {
            x += ax & -(*dir == 'R');
            w += aw & -(*dir == 'L');
            y += ay & -(*dir == 'D');
            h += ah & -(*dir == 'U');
        }

        px = x + (w - x)/2;
        py = y + (h - y)/2;

        printf("%d %d\n", px, py);
    }
    return 0;
}

Ce code propose la même approhe dichotomique que la mienne.
Néanmois, cette solution a attiré mon regard car le nouvel intervalle est calculé et appliqué à chaque itération, lorsqu’il est appliqué, un masque est utilisé sur les nouvelles bornes max et min (des axes x et y) en fonction de si dir contient ou non le charactère souhaité.

5. Bilan

Après avoir analyser le problème, je l’ai trouvé plutôt simple à résoudre et je n’ai pas rencontré de difficultés.