Heat Detector

The aim of this puzzle is to find a bomb, hidden on one cell of a grid. Each turn, you get to move wherever you want on the grid, and you get the direction of the bomb based on your position (up, down, left, up-right, etc). As explained in the code, a solution is to run a binary search. In other words, you move so that each indication allows you to narrow down (by half, or more) the number of possible locations where the bomb could be.

C

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. int main(int argc, char** argv) {
  5.     int W, H, turns, x, y; 
  6.     scanf("%d %d\n%d\n%d %d\n", &W, &H, &turns, &x, &y);
  7.  
  8.     // these 4 variables circumscribe a zone where the bomb is
  9.     int xInf = 0;
  10.     int xSup =  W-1;
  11.     int yInf = 0;
  12.     int ySup = H-1;
  13.  
  14.     /* each turn, we go to the center of this zone, and the direction provided
  15.     allows us to narrow down the zone .
  16.     It is like a 2 dimensional binary search.*/
  17.  
  18.     char BD[2] = { ' ', ' ' };
  19.     while (1) {
  20.         scanf("%s", BD);
  21.  
  22.         if (BD[0] == 'U')
  23.             ySup = y-1;
  24.         else if (BD[0] == 'D')
  25.             yInf = y+1;
  26.         else
  27.             ySup = yInf = y; 
  28.             
  29.         if (BD[0] == 'R' || BD[1] == 'R')
  30.             xInf = x+1;
  31.         else if((BD[0] == 'L') || (BD[1] == 'L'))
  32.             xSup = x-1;
  33.         else
  34.             xSup = xInf = x;
  35.             
  36.         x = (xInf + xSup)/2;
  37.         y = (yInf + ySup)/2;
  38.         printf("%d %d\n", x, y);
  39.     }
  40.  
  41.     return EXIT_SUCCESS;
  42. }
  43.