Locked deep down

Computer Science Level 5

Do you like carrots? Do you like carrots?

Given this 100 × 38 100 \times 38 maze with two exits, find out the number of steps (left, right, up and down), including the step out of the maze, from the worst point inside, i.e, the point from which it takes the longest to get out.

The maze is presented in an obvious format. Absence of | or - represent absence of walls. Walls on the boundaries which are absent are exits.

To clarify, the title image is a joke. It has got nothing to do with the maze the problem links to .

Example

The worst point of the following 3 × 5 3 \times 5 maze is the lower left corner. It takes 9 steps to get out from that point 

1
2
3
4
5
6
7
 
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+


The answer is 168.

View wiki
Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Laurent Shorts
Mar 27, 2016

Maze longest path

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Just go around the maze...

Justin Adrian Halim - 5 years, 2 months ago

Log in to reply

Nive idea but you're locked inside

Agnishom Chattopadhyay - 5 years, 2 months ago

Did you do that by hand?

Agnishom Chattopadhyay - 5 years, 2 months ago

Log in to reply

I made a program in Python to get the answer. It wasn't difficult to add some lines to it to have it showing the path.

Laurent Shorts - 5 years, 2 months ago

Log in to reply

Oh that's cool. You might want to add the program to your solution

Agnishom Chattopadhyay - 5 years, 2 months ago
Mathieu Guinin
Apr 9, 2016 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
 
#include <stdlib.h>
#include <stdio.h>

/******** UGLY MANUAL CONFIGURATION *********/
#define WIDTH 38
#define HEIGHT 100
/********************************************/

#define W (2*WIDTH+2)
#define H (2*HEIGHT+1)
#define Infinity 1000000000

char    maze[H][W];
int min_depth[HEIGHT][WIDTH];

// go deeper in the maze recurcively in every directions where min depth should be updated 
void    deeper_inside(int i, int j, int depth)
{
    if (i >= 0 && i < WIDTH && j >= 0 && j < HEIGHT && min_depth[j][i] > depth)
    {
        int x = 2*i + 1;
        int y = 2*j + 1;

        min_depth[j][i] = depth;

        if (maze[y][x-1] == ' ')
            deeper_inside(i-1, j, depth + 1);
        if (maze[y][x+1] == ' ')
            deeper_inside(i+1, j, depth + 1);
        if (maze[y-1][x] == ' ')
            deeper_inside(i, j-1, depth + 1);
        if (maze[y+1][x] == ' ')
            deeper_inside(i, j+1, depth + 1);
    }
}

// search an exit alongside of a border
void    search_exits(int x, int y, int dx, int dy)
{
    while (x < W-1 && y < H)
    {
        if (maze[y][x] == ' ')
            deeper_inside((x-1) / 2, (y-1) / 2, 1);
        x += dx;
        y += dy;
    }
}

// print the maze with min depths
void    print_maze()
{
    int x;
    int y;
    char    c;
    int depth;

    for (y = 0; y < H; y++)
    for (x = 0; x < W; x++)
    {
        c = maze[y][x];
        if ((x & 1) && c == ' ')
        {
            depth = min_depth[(y-1) / 2][(x-1) / 2];
            if ((y & 1) == 0)
                printf("   ");
            else if (depth < Infinity)
                printf("%3d", depth);
            else
                printf(" X ");
        }
        else if (c == '-')
            printf("---");
        else
            putchar(c);
    }
}

int main()
{
    int *i;
    int worst;

    read(0, maze, W*H);

    //init each cell with an infinit depth (=unexplored)
    i = (int *)&min_depth[HEIGHT-1][WIDTH];
    while (i-- != (int *)min_depth)
        *i = Infinity;

    //search all the exits on the 4 outside walls and explore the maze !
    search_exits(1, 0, 2, 0);
    search_exits(0, 1, 0, 2);
    search_exits(W - 2, 1, 0, 2);
    search_exits(1, H - 1, 2, 0);

    //find the worst depth
    worst = 0;
    i = (int *)&min_depth[HEIGHT-1][WIDTH];
    while (i-- != (int *)min_depth)
        if (*i > worst && *i != Infinity)
            worst = *i;

    print_maze();
    printf("\nThe worst point is at %d of an exit\n", worst);
    return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...