c++ - TopCoder "Escape"解决困惑

Question

这是在 TopCoder 竞赛中使用的问题。我了解大部分解决方案，它本质上是在任何时间点跟踪特定节点的最佳解决方案，并且在到达目标节点后可以输出最佳解决方案。但是，该解决方案使用 BFS，我很困惑，因为似乎可以多次访问同一个节点，所以我只是想了解代码是如何工作的。我知道有一个终止条件，但我们如何确保目的地将拥有最佳解决方案，如果 BFS 过程没有“访问”数组，我们如何确保代码实际上终止(即使有终止条件)？我在下面附上了问题陈述和解决方案。

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

这一行:

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

表示“如果位置 dest 不在计算的距离 map 中，或者如果我们找到一条更便宜的新路径，则探索它”。此条件确保 BFS 终止。