Cómo resolver Maze Runner en C

El reto

Introducción

Welcome Adventurer. Your purpose is to navigate the maze and attain the end level with out touching any partitions. Doing so will kill you immediately!

Tarea

You may be given a 2D array of the maze and an array of instructions. Your activity is to comply with the instructions given. When you attain the top level earlier than all of your strikes have gone, you must return End. When you hit any partitions or go exterior the maze border, you must return Lifeless. If you end up nonetheless within the maze after utilizing all of the strikes, you must return Misplaced.

La matriz Maze se verá como

maze = ((1,1,1,1,1,1,1),
        (1,0,0,0,0,0,3),
        (1,0,1,0,1,0,1),
        (0,0,1,0,0,0,1),
        (1,0,1,0,1,0,1),
        (1,0,0,0,0,0,1),
        (1,2,1,0,1,0,1))

..con la siguiente clave

0 = Protected place to stroll
      1 = Wall
      2 = Begin Level
      3 = End Level

  instructions = "NNNNNEEEEE" == "End" // (instructions handed as a string)

Normas

1. The Maze array will all the time be sq. i.e. N x N however its measurement and content material will alter from take a look at to check.

2. The beginning and end positions will change for the ultimate assessments.

3. The instructions array will all the time be in higher case and will likely be within the format of N = North, E = East, W = West and S = South.

4. When you attain the top level earlier than all of your strikes have gone, you must return End.

5. When you hit any partitions or go exterior the maze border, you must return Lifeless.

6. If you end up nonetheless within the maze after utilizing all of the strikes, you must return Misplaced.

La solución en C

Opción 1:

#embody <stddef.h>

char *maze_runner(const int *maze, size_t n, const char *instructions) 
{
  int x, y, cur;
  
  // find the beginning
  for (y = 0; y < n; y++) for (x = 0; x < n; x++) if (maze(y*n+x) == 2) goto strikes;
  
  strikes:
  for (char *d = instructions; *d; d++) 
  {
    change (*d) {
      case 'N': y--; break;
      case 'S': y++; break;
      case 'E': x++; break;
      case 'W': x--; break;
    }
    if (x < 0 || y < 0 || y > n-1 || x > n-1)  return "Lifeless"; // out of bounds
    if ((cur = maze(y*n+x)) == 1)              return "Lifeless"; // hit wall 
    if (cur == 3)                              return "End"; // discovered exit
  }
  
  return "Misplaced";
}

Opcion 2:

#embody <stddef.h>
#embody <iso646.h>

#outline NORTH 'N'
#outline SOUTH 'S'
#outline EAST  'E'
#outline WEST  'W'

#outline START   2
#outline WALL    1
#outline FINISH  3

char *maze_runner(const int *maze, size_t n, const char *instructions) {
    size_t x, y;
    for (size_t i = 0; i < n; i++){
        for (size_t j = 0; j < n; j++)
            if (maze(i * n + j) == START){
                x = j;
                y = i;
            }
    }
    for (size_t i = 0; instructions(i); i++){
        x += (instructions(i) == EAST) - (instructions(i) == WEST);
        y += (instructions(i) == SOUTH) - (instructions(i) == NORTH);
        if (maze(y * n + x) == WALL or x >= n or y >= n)
            return "Lifeless";
        if (maze(y * n + x) == FINISH)
            return "End";
    }
    return "Misplaced";
}

Opción 3:

#embody <stddef.h>

#outline DEAD(N, MAX) N < 0 || N > MAX - 1

void transfer(int *x, int *y, char dir) {
  change (dir) {
      case 'N': *y -= 1; break;
      case 'S': *y += 1; break;
      case 'E': *x += 1; break;
      case 'W': *x -= 1; break;
  }
}

char *maze_runner(const int *maze, size_t n, const char *instructions) {
  int nums(n)(n), x, y, i, *p;

  for (p = maze, i = 0; i < n * n; i++) {
    nums(i/n)(ipercentn) = maze(i);
    if (*p++ == 2) x = ipercentn, y = i/n;
  }

  whereas (*instructions) 

  return "Misplaced";
}

Casos de prueba para validar nuestra solución

#embody <criterion/criterion.h>

void tester(const int *maze, size_t n, const char *instructions, char *end result);

Check(Example_Tests, should_pass_all_the_tests_provided) {

    #outline N 7

    const int maze(N * N) = {1, 1, 1, 1, 1, 1, 1,  
                             1, 0, 0, 0, 0, 0, 3, 
                             1, 0, 1, 0, 1, 0, 1,
                             0, 0, 1, 0, 0, 0, 1,    
                             1, 0, 1, 0, 1, 0, 1,
                             1, 0, 0, 0, 0, 0, 1,
                             1, 2, 1, 0, 1, 0, 1};
  
  //  maze is handed in as a 1-D int array with size n
  //  instructions are handed in as a null-terninated string
  //  don't allocate reminiscence, as a substitute return a string literal
  
  { const char *instructions = "NNNNNEEEEE";     tester(maze, N, instructions, "End"); }
  { const char *instructions = "NNNNNEESSEENNE"; tester(maze, N, instructions, "End"); }
  { const char *instructions = "NNNNNEEEEEWW";   tester(maze, N, instructions, "End"); }
  { const char *instructions = "NEEEE";          tester(maze, N, instructions,   "Misplaced"); }
  { const char *instructions = "NNNWW";          tester(maze, N, instructions,   "Lifeless"); }
  { const char *instructions = "NNNNNEESSSSSS";  tester(maze, N, instructions,   "Lifeless"); }
  
}