找到你要的答案

Q:TopCoder “Escape” solution confusion

Q:TopCoder“逃离”解困惑

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()];
}

};

这是一个问题,作为一个个人竞争。我理解大部分的解决方案,它本质上是在任何时间点跟踪特定节点的最佳解决方案,到达目的节点之后可以输出最佳的解决方案。然而,该解决方案采用BFS,我很困惑,因为它似乎是相同的节点可以访问多次,所以我只是试图理解代码是如何工作的。我知道有一个终止条件,但我们如何确保目标将最好的解决方案,如果没有“参观”的BFS程序阵列,我们如何确保代码将终止,事实上,(即使有一个终止条件)?我已经附上下面的问题陈述和解决方案。

问题陈述

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:

输入格式(报价清晰):“x1 y1 x2 y2(x1,y1)”,是该地区一角(X2,Y2)是该地区的另一个角落

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()];
}

};
answer1: 回答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.

这条线:

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

说:“如果不在计算距离地图探索位置的桌子,或者如果我们发现一个更便宜的新路径”。这个条件保证BFS终止。

c++  algorithm  breadth-first-search