TopCoder "Escape" solution confusion

Question

This is a question that was used in a TopCoder competition. I understand most of the solution, which essentially keeps track of the best solution to a particular node at any point in time and upon reaching the destination node can then output the best solution to that. However, the solution uses BFS, and I'm confused because it seems like the same node can be visited multiple times, so I'm just trying to comprehend how the code is working. I know there is a termination condition, but how do we ensure that the destination will hold the best solution and, if there is no "visited" array for the BFS procedure, how can we ensure that the code will, in fact, terminate (even though there is a termination condition)? I've attached the problem statement and solution below.

Problem Statement

You are playing a video game that involves escaping from a dangerous area. Within the area there are DEADLY regions you can't enter, HARMFUL regions that take 1 life for every step you make in them, and NORMAL regions that don't affect you in any way. You will start from (0,0) and have to make it to (500,500) using only Up, Left, Right, and Down steps. The map will be given as a String[] deadly listing the DEADLY regions and a String[] harmful listing the HARMFUL regions. The elements in each of these parameters will be formatted as follows:

Input format(quotes for clarity): "X1 Y1 X2 Y2" where (X1,Y1) is one corner of the region and (X2,Y2) is the other corner of the region

The corners of the region are inclusive bounds (i.e. (4,1) and (2,2) include x-values between 4 and 2 inclusive and y-values between 1 and 2 inclusive). All unspecified regions are considered NORMAL. If regions overlap for a particular square, then whichever region is worst takes effect (e.g. DEADLY+HARMFUL = DEADLY, HARMFUL+NORMAL = HARMFUL, HARMFUL+HARMFUL = HARMFUL, DEADLY+NORMAL=DEADLY).

Damage taken at each step occurs based on the destination square and not on the starting square (e.g. if the square (500,500) is HARMFUL you WILL take a point of damage stepping onto it; if the square (0,0) is HARMFUL you WON'T take a point of damage stepping off of it; this works analogously for DEADLY squares).

Return the least amount of life you will have to lose in order to reach the destination. Return -1 if there is no path to the destination. Your character is not allowed to leave the map (i.e. have X or Y less than 0 or greater than 500).

#include <iostream>
#include <limits>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <strstream>
using namespace std;

struct node
{
  node(int _x, int _y) {x = _x; y = _y;}

  int id() const
  {
    return y*501+x;
  }

  int x, y;
};

map <int, int> dist;

bool operator<(const node &n1, const node &n2)
{
  if (dist[n1.id()] != dist[n2.id()])
    return dist[n1.id()] < dist[n2.id()];
  return n1.id() < n2.id();
}


class Escape
{
public:

int grid[501][501];

void clear(int x1, int y1, int x2, int y2, int val)
{
  int tx;
  if (x2 < x1)
  {
    tx = x1;
    x1 = x2;
    x2 = tx;
  }
  if (y2 < y1)
  {
    tx = y1;
    y1 = y2;
    y2 = tx;
  }
  for (int y = y1; y <= y2; y++)
  for (int x = x1; x <= x2; x++)
  {
    grid[y][x] = val;
  }
}

void bfs(int srcx, int srcy)
{
  node src(srcx, srcy);
  set <node> totry;
  dist.clear();
  dist[src.id()] = 0;
  totry.insert(src);

  int x = 0;
  while (totry.size())
  {
    srcx = totry.begin()->x;
    srcy = totry.begin()->y;
    src = node(srcx, srcy);
/*    cout 
    x++;*/

    for (int dstx = srcx-1; dstx <= srcx+1; dstx++)
    for (int dsty = srcy-1; dsty <= srcy+1; dsty++)
    if (dstx >= 0 && dsty >= 0 && dstx <= 500 && dsty <= 500)
    if ( (dstx-srcx)*(dstx-srcx) + (dsty-srcy)*(dsty-srcy) == 1)
    {
      node dest(dstx, dsty);
      int length = grid[dsty][dstx];
      if (length < 2)
      if (!dist.count(dest.id()) || dist[dest.id()] > dist[src.id()] + length)
      {
        dist[dest.id()] = dist[src.id()] + length;
        totry.insert(dest);
      }
    }
    totry.erase(src);
  }
}

int lowest(vector<string> harmful, vector<string> deadly)
{
  int i;

  clear(0,0,500,500, 0);
  for (i = 0; i < harmful.size(); i++)
  {
    istrstream in(harmful[i].c_str());
    int x1, y1, x2, y2;
    in >> x1 >> y1 >> x2 >> y2;
    clear(x1, y1, x2, y2, 1);
  }
  for (i = 0; i < deadly.size(); i++)
  {
    istrstream in(deadly[i].c_str());
    int x1, y1, x2, y2;
    in >> x1 >> y1 >> x2 >> y2;
    clear(x1, y1, x2, y2, 2);
  }

  bfs(0, 0);


  node end = node(500,500);
  if (!dist.count(end.id()))
    return -1;
  else
    return dist[end.id()];
}

};

Answer 1

This line:

if (!dist.count(dest.id()) || dist[dest.id()] > dist[src.id()] + length)

is saying "explore location dest if it is not in the calculated distances map, or if we found a new cheaper path to it". This condition ensures that the BFS terminates.