Shadows of the knight Ep.2

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

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 l’on s’est approché, éloigné ou resté à la même distance de la bombe par rapport à notre position précédente.
Le but est de trouver la bombe en le moins de déplacements possible.

2. Approches utilisées

2.1. Tentative 1

J’ai d’abord essayé de résoudre le problème en utilisant une approche dichotomique, sans information sur la direction vers la bombe, celle-ci n’a pas abouti

2.2. Tentative 2

J’ai ensuite essayé d’utiliser un talbeau en 2 dimensions, chaque valeur étant 0 ou 1 pour une position de fenêtre. Si la fenêtre ne peut pas contenir la bombe, elle est marquée 0, sinon 1.
A chaque itération, on itère sur tout le tableau et on marque des fenêtres à 0 en fonction de l’information donnée (Warmer, Colder ou Same). On répète ceci jusqu’à ce qu’il reste une seule casé marquée à 1.
Cette solution n’a pas abouti non plus, par mon manque de compréhension pour comment actualiser le tableau en fonction de l’information et par son manque d’optimisation.

3. Comparaison avec une autre solution

A partir de cette solution externe :

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

struct {int lo,hi;} warm, cold;
int W, H, N, x, y, px, py, lo, hi;
int found_x = 0, outside = 0;

int found(){
    if (found_x) y=(lo+hi) / 2;   // found y
    else {
        found_x = 1;
        x=(lo+hi) / 2;           // found x, start search for y
        lo=0; hi=H-1;
        warm.lo = 0; warm.hi = hi;
        cold.lo = 0; cold.hi = hi;
    }
    return x==px && y==py;      // calc next pos if already output
}

int get(int value, int limit){
    int res = lo + hi - value;
    if (outside){               // take halfway point if was outside
        if (value==0)     res = res / 2;
        if (value==limit) res = (limit+res) / 2;
        outside = 0;
    }
    if (res==value) res++;
    if (res<0)      outside=1, res=0;
    if (res>limit)  outside=1, res=limit;

    int l2 = (res+value-1)>>1, h2 = (res+value+1)>>1;
    if (res>value) warm.lo = h2, warm.hi = hi, cold.lo = lo, cold.hi = l2;
    else           warm.lo = lo, warm.hi = l2, cold.lo = h2, cold.hi = hi;
    return res;
}

int main(){
    scanf("%d%d", &W, &H);
    scanf("%d", &N);
    scanf("%d%d", &x, &y);

    lo = 0, hi = W;
    warm.lo = 0; warm.hi = hi;
    cold.lo = 0; cold.hi = hi;

    while (1) {
        px = x; py = y;
        char dir[11];
        scanf("%s", dir);
        if (dir[0]=='W') lo=warm.lo, hi=warm.hi;
        if (dir[0]=='C') lo=cold.lo, hi=cold.hi;
        if ((dir[0]=='S' || lo>=hi) && !found()){}
        else {
            if (found_x) y=get(y,H-1);
            else         x=get(x,W-1);
        }
        printf("%d %d\n", x,y);
    }
}

Cette solution propose de trouver la position de la bombe axe par axe, d’abord l’axe x en cherchant la position la plus proche de la bombe, puis l’axe y en faisant de même.
Cette solution utilise de la dichotomie.

4. Bilan

Bien que j’ai réussi à comprendre le problème assez rapidement et trouvé une méthode de résolution (trilatération), j’ai eu du mal à l’implémentée et ai essayé d’autres méthodes de résolution qui n’ont pas abouti.