The Lost Woods - Lazy Hearts

Computer Science Level 4

Our hero, Link, finds himself in a forest most plain. Scattered around him, northways, eastways, westways and southways, are open plots of grass, impenetrable woods, and scattered, rare Heart Pieces. This time, we wonder if Link can get just one of these Heart Pieces, and if so, how many steps he needs to take to reach it.

This link (1) contains a zip file, with a single file in the Input Format specified for this collection of problems, of $1000$ mazes.

Let $S$ be the sum of the score for each maze. We define the score to be the index of the maze (1-based) multiplied by the minimum number of steps Link must take to reach a single Heart Piece, if he can. If no Heart Piece can be reached, the score for that maze is zero.

Find $\boxed{S}$ .

Example:

Input:

3
6 1
H.L..H
2 2
L#
#H
5 5
L....
####.
..H#.
.###.
.....

Output:

Output Explained:

In the first maze, there is are two Heart Pieces, but the one on the left is closer, at $2$ steps away instead of $3$ , so the score for the maze is $1$ (the index) times $2$ .

In the second maze, there is a single Heart Piece, but it cannot be accessed, so the score for that maze is zero.

In the third maze, there is a single Heart Piece, and it is reachable in precisely $16$ steps, so the score for this maze is $48$ .

$2 + 48 = \boxed{50}$

Details:

Link will always appear once per maze, as an 'L'.
There will be a positive number of Heart Pieces per maze, as 'H'.
Open ground is given as '.'.
Impenetrable trees are given as '#'.
No other characters will be present in each maze.
$1 \leq W,H \leq 100$ in all mazes.

(1) - This link currently points to my Dropbox account, since there is currently no way to upload non-image content to Brilliant. Admin, feel free to delete this footnote if this is changed.

This is a part of the collection entitled The Lost Woods , a series of problems in CS / Graph Theory

Image Credit: http://www.gamesradar.com/lost-woods-how-zeldas-enchanted-groves-inspired-forest-puzzling-mazes/

The answer is 10130290.

2 solutions

Resha Dwika Hefni Al-Fahsi
Jan 18, 2017

This problem is the implementation of Dijkstra's Algorithm , Here is the C++ solution:

#include<bits/stdc++.h>

#define inf 9999
typedef std::pair<long long,long long> ll;

std::queue<ll> qxy,qgoal;
long long dx[]={1,0,-1,0};
long long dy[]={0,1,0,-1};
char map[10000][10000];
long long plot[10000][10000];

int main(){

long long m,n;
long long max,sum=0;

std::cin>>max;

for(long long s=1;s<=max;s++){

std::cin>>m>>n;   

    for(long long x=0;x<n;x++)
        for(long long y=0;y<m;y++){
            plot[x][y]=inf;
            std::cin>>map[x][y];
            if(map[x][y]=='H'){
                ll v; 
                    v.first=x; 
                    v.second=y;

                qgoal.push(v);
                }
            if(map[x][y]=='L'){ 
                ll w;
                    w.first=x;
                    w.second=y;
                plot[x][y]=0;
                qxy.push(w);
        }
   }

    while(!qxy.empty()){
        ll z=qxy.front(); qxy.pop();

        for(long long i=0;i<4;i++){

            if( ((z.first+dx[i])>=0) && ((z.second+dy[i])>=0) && ((z.first+dx[i])<n) && ((z.second+dy[i])<m) && (map[(z.first+dx[i])][(z.second+dy[i])]!='#')
               && ((plot[(z.first+dx[i])][(z.second+dy[i])])>(plot[z.first][z.second])+1) ){

                plot[(z.first+dx[i])][(z.second+dy[i])] = plot[z.first][z.second] + 1;
                qxy.push(std::make_pair((z.first+dx[i]),(z.second+dy[i])));

               }    

        }   
    }

    int min=inf;
    while(!qgoal.empty()){
        ll a=qgoal.front(); qgoal.pop();
        if(plot[a.first][a.second]<=min) min=plot[a.first][a.second];
    }

    if(min==inf) min=0;


sum+=(min*s);

}

std::cout<<sum<<std::endl;

}

Daniel Ploch
Jan 15, 2016

Similarly as with 'Finding Hearts' , Graph Traversal is the key to solving this problem, only this time, we need to remember how many steps we're taking to get to traversed nodes in a consistent manner. Starting from Link's location, we can initiate a plain old BFS , or Dijkstra's Algorithm , which is equivalent when all of the edge weights are identical. We can short-circuit the algorithm once we find a Heart Piece, and if we wind up with none, we return nothing.

Pseudo Code:

steps = 0
visited = set[link]
node_list = [link]
while node_list is not empty:
  steps++
  new_node_list = []
  for node in node_list:
    for adj_node in node.adjacent_nodes():
      if adj_node.value == 'H':
        answer += index * steps
        exit_while_loop
      if adj_node.value == '.' and adj_node not in visited:
        visited.add(adj_node)
        new_node_list.add(adj_node)
  node_list = new_node_list

Click this link to view the scores for each maze from the input in order, sans multiplication by the index. If you were not able to get the right answer, consulting these individual results may help you find the problem (or, if I got something wrong, the bug in my own solution!)

The Lost Woods - Lazy Hearts

This is a part of the collection entitled The Lost Woods , a series of problems in CS / Graph Theory

Image Credit: http://www.gamesradar.com/lost-woods-how-zeldas-enchanted-groves-inspired-forest-puzzling-mazes/

The answer is 10130290.

2 solutions

0 pending reports