Rapport Shadows of the Knight - Episode 1
Table of Contents
1. Présentation du puzzle
L’objectif de ce puzzle est d’aider batman à trouver la bombe dans la grille le plus rapidement possible. Le nombre de déplacement doit donc être minimale pour retrouver la bombe. A chaque déplacement on obtient une information sur ou se positionne la bombe par rapport à batman. On retrouve en entrée deux entiers W,H pour width=largeur et Height=height. Un entier N qui représente le nombre de sauts avant que les bombes n’explosent. Et enfin deux entiers X0 et Y0 qui sont la position de départ de batman. Les différentes informations possible pour chaque tour sont :
- U pour upper = la bombe est au-dessus
- UR pour upper-right = la bombe est au-dessus et à droite
- UL pour upper-left = la bombe est au-dessus et à gauche
- D pour down = la bombe est en dessous
- DL pour down-left = la bombe est en dessous et à gauche
- DR pour down-right = la bombe est en dessous et à droite
- R pour right = la bombe est à droite
- L pour left = la bombe est à gauche
2. Présentation de ma méthode de résolution
2.1. synopsis
Pour réaliser ce puzzle j’ai utilisé la recherche dichotomique afin de minimiser le nombre de sauts de batman. L’idée centrale de l’approche dichotomique repose sur l’idée de réduire de moitié l’espace de recherche à chaque étape : on regarde la valeur du milieu et si ce n’est pas celle recherchée, on sait qu’il faut continuer de chercher dans la première moitié ou dans la seconde. Dans notre cas on fera une double dichotomie. Une pour la nouvelle ordonnée et une pour la nouvelle abcisse.
2.2. Description algorithmique
Je vais définir à chaque tour un nouveau rectangle grâce aux informations données. Chaque itération de la boucle while représente un tour. Je vais donc grâce a ces informations réduire mon ancien rectangle de recherche. Si la bombe est au dessus alors mon rectangle sera mon ancien rectangle enlevée de toute les case en dessous de batman. De la même façcon pour la bombe en dessous je supprime les cases au dessus de batman. Et ainsi de suite pour la droite et la gauche. Cependant on peut obtenir les informations : U,D,R,L qui nous donne plus d’informations que les autres. Celle-ci nous permette de réduire grandement le rectangle. Si U est donnée alors la bombe se situe sur la colonne que batman et la bombe est au dessus de lui. De la même façon pour les autres informations à caractère unique. Ensuite je place batman au centre de ce nouveau rectangle. J’obtiendrais donc ensuite une information qui divisera par 4 mon ancien rectangle.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main(){ int W; /*Variable de la largeur du batiment*/ int H; /*Variable de la hauteur du batiment*/ scanf("%d%d", &W, &H); /*Récuperation de ces variables en entrée*/ int N; /*Variable du nombre de coup max*/ scanf("%d", &N); int X0; /*Variables contenant la position de départ de batman*/ int Y0; scanf("%d%d", &X0, &Y0); int xinf=0,xsup=W-1,yinf=0,ysup=H-1; /*initialisation de variable permettant de réduire notre recherche dans le batiment*/ while (1) { char bomb_dir[4]; scanf("%s", bomb_dir); /*Récuperation de l'information de la position de la bombe par rapport à batman*/ if (bomb_dir[0]=='U'){ ysup=Y0-1; /*Si la bombe est au dessus alors la borne supérieur de recherche en ordonnée est modifié pour savoir dans quel rectangle se situe la bombre*/ if (bomb_dir[1]!='R' && bomb_dir[1]!='L'){ /* Si la bombre est pile au dessus alors la bombe est sur la meme colonne*/ xinf=X0; xsup=X0; } }else if(bomb_dir[0]=='D'){ /*De la même façon pour en dessous*/ yinf=Y0+1; if (bomb_dir[1]!='R' && bomb_dir[1]!='L'){ xinf=X0; xsup=X0; } } if (bomb_dir[0]=='R' || bomb_dir[1]=='R'){ /*test pour la bombe à droite*/ xinf=X0+1; if (bomb_dir[0]=='R'){ yinf=Y0; ysup=Y0; } }else if(bomb_dir[0]=='L' || bomb_dir[1]=='L'){ /*test pour la bombe à gauche*/ xsup=X0-1; if (bomb_dir[0]=='L'){ yinf=Y0; ysup=Y0; } } X0=xinf+(xsup-xinf+1)/2; /*On place batman au centre de notre nouveau rectangle*/ Y0=yinf+(ysup-yinf+1)/2; printf("%d %d\n",X0,Y0); } return 0; }
3. Une autre méthode
3.1. Description
L’idée de réduire le rectangle par dichotomie reste dans ce code. Cependant l’utilisation de switch pour les test est intérressant car plus simple à comprendre que toutes mes conditions.
#include <stdio.h> int main() { int W; // width of the building. int H; // height of the building. scanf("%d%d", &W, &H); int N; // maximum number of turns before game over. scanf("%d", &N); int X0; int Y0; scanf("%d%d", &X0, &Y0); int xmin = 0 ; int xmax = W ; int ymin = 0 ; int ymax = H ; // game loop while (N--) { char bombDir[4]; // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL) scanf("%s", bombDir); switch (bombDir[0]) { case 'U' : ymax = Y0 ; break ; case 'D' : ymin = Y0 ; break ; case 'R' : xmin = X0 ; break ; case 'L' : xmax = X0 ; break ; } switch (bombDir[1]) { case 'R' : xmin = X0 ; break ; case 'L' : xmax = X0 ; break ; } Y0 = (ymax + ymin)/2 ; X0 = (xmin + xmax)/2 ; printf("%d %d\n", X0, Y0); } }
4. Apprentissage
J’ai compris comment fonctionner la dichotomie en 2D, l’utilisation de switch aurait pu aider à mieux comprendre le code mais je trouve avoir utilisé une bonne méthode de résolution.