Problem analysis

  • The only difficulty of this problem is:

      • The coordinates of the grid is negative

      • Array indices in most programming languages are 0 or positive

  • Simple fix: 

    int grid[500][300];  // More than enough...

              <------------- x --------------->
             |
	   y |
	     V

#define x(i) ((i) + 250)  // Translates negative x-coord
#define y(i) ((i) + 250)  // Translates negative y-coord

Data representation

  

 Grid:

      int grid[500][300];  // More than enough...

 Representation:

      grid[x][y] = 0   --> no tunnel at (x,y)
      grid[x][y] = 1   --> (x,y) is part of tunnel

 Current position:

      int currX = 0, currY = 0;

digDown(n)    dig down n positions 

void digDown(int n)
{
   bool danger = false;

   for ( int i = 1; i <= n; i++ )
   {
      if ( grid[x(currX)][y(currY-1)] == 1 )
         danger = true;

      grid[x(currX)][y(currY-1)] = 1;  // Mark position as part of tunnel
      currY--;           // Go further
   }

   if ( !danger )
      cout << (currX) << " " << (currY) << " safe" << endl;
   else
   {
      cout << (currX) << " " << (currY) << " DANGER" << endl;
      exit(0);
   }
}

digUp( ), digLeft( ) and digRight( ) are similar...

Initialization

  

void makeInitGrid(int grid[500][300])
{
   digDown(3);
   digRight(3);
   digDown(2);
   digRight(2);
   digUp(2);
   digRight(2);
   digDown(4);
   digLeft(8);
   digUp(2);
}



      00010000000000
      00010000000000
      00011110111000
      00000010101000
      00100011101000
      00100000001000
      00111111111000
      00000000000000

Solution for J4 

   while ( true )
   {
      cin >> dir;
      cin >> steps;

      if ( dir == 'q' )
          break;

      switch ( dir )
      {
         case 'l': digLeft(steps);
                   break;
         case 'r': digRight(steps);
                   break;
         case 'u': digUp(steps);
                   break;
         case 'd': digDown(steps);
                   break;
      }
   }