Skating shortest path

Level pending

Sally is a very bad skater, she can only skate in one direction! But Sally still wants to find her dad in the least amount of moves possible so that she can get off the ice. Sally's only way of stopping are walls.

(#) -- Wall

(.) -- Free space

(S) -- Sally's starting position

(D) -- Dad's position

Example

Find the sum of the shortest paths of these five 20x20 ice rinks. Ice rinks are separated by hyphens. Text file with ice rinks


The answer is 232.

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.

1 solution

First I loaded the rink files into an array of strings: rinks[n][y] = y-th line of rink #n, with n = 0 .. 4 and y = 0 .. 19.

 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
int dx[] = { 1, 0, -1,  0 };      // The directions in which Susy can skate.
int dy[] = { 0, 1,  0, -1 };

int sum = 0;
for (int rink = 0; rink < 5; rink++) {
    int spath[][] = new int[22][22];                // We use a rink of 22x22, because we add a wall around it.

// spath[x][y] = -2 for a wall; -1 for a freely accessible position;
// and spath[x][y] = n >= 0 means that Susy can get there and stop there in n steps.

    boolean isnew[][] = new boolean[22][22];    // Which positions must we consider for further investigation?

    int sx = 0, sy = 0; 

    for (int x = 0; x < 22; x++) for (int y = 0; y < 22; y++) {   // First make everything a "wall".
            spath[x][y] = -2;
            isnew[x][y] = false;
    }

    for (int x = 1; x <= 20; x++) for (int y = 1; y <= 20; y++) {  // Copy the shape of the rink.
        char c = rinks[rink][y-1].charAt(x-1);

        if (c == '.' || c == 'D') spath[x][y] = -1;
        if (c == 'S') { spath[x][y] = 0; isnew[x][y] = true; }  // starting point
        if (c == 'D') { sx = x; sy = y; }   // (sx, sy) = Daddy's position
    }

    boolean changed = true;
    while (changed) {
        changed = false;   // We keep going until nothing changes.

        for (int x = 1; x <= 20; x++) for (int y = 1; y <= 20; y++)
            if (isnew[x][y]) {
                isnew[x][y] = false;   // Start at the positions marked as "new".

                for (int d = 0; d < 4; d++) {   // Skate in each direction ...
                    int xx = x, yy = y;

                    int l = 0;
                    while (spath[xx][yy] > -2) {     // ... until Susy hits a wall.
                        xx += dx[d]; yy += dy[d]; l++; 
                    }
                    xx -= dx[d]; yy -= dy[d]; l--;   // Then move one step back. 'l' = number of steps.

                    if (l > 0) {        // Did we move at all?
                        if (spath[xx][yy] == -1 ||
                            spath[x][y]+l < spath[xx][yy]) {    // Is the number of steps better than what we already has?
                                isnew[xx][yy] = true;
                                spath[xx][yy] = spath[x][y] + l;   // If so, update the number and mark the position as 'new'.
                                changed = true;
                        }
                    }
                }
            }
    }

    out.println(spath[sx][sy]);       // Read off the value at Daddy's position.
}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...