时间戳

首页 > 解决方案 > 我对网格旅行者问题的实现仅适用于小网格

c++ - 我对网格旅行者问题的实现仅适用于小网格

问题描述

我在 38:39 尝试在这个免费的代码营视频中解决这个问题：https ://youtu.be/oBt53YbR9Kk?t=2361

问题如下：

假设您是 2D 网格上的旅行者。你从左上角开始，你的目标是到达右下角。您只能向下或向右移动。

您可以通过多少种方式到达尺寸为 m*n 的网格上的目标

编写一个计算这个的函数 GridTraveller(m,n)。

我的尝试给出了除 18 x 18 网格之外的所有内容的正确答案，这是我的代码：

#include <iostream>
#include <map>


struct grid {
  unsigned long long int x,y;
  grid(unsigned long long int x_c, unsigned long long  int y_c):x(x_c),y(y_c){};

 bool operator< (const grid& rhs) const {
    return (x + y < rhs.x+rhs.y);

}
};



unsigned long long int grd_traveller(grid grd, std::map <grid,unsigned long long int> &mem){
  if (mem.count(grd) != 0){
    return mem[grd];
  }
  else if (grd.x ==1 || grd.y ==1){
    return 1;
  }

  else if (grd.x==0 || grd.y ==0){
    return 0;
  }
  else {
    grid iter1(grd.x-1,grd.y);
    grid iter2(grd.x,grd.y-1);

    unsigned long long int answer =  grd_traveller(iter1,mem) + grd_traveller(iter2,mem);
    mem[grd] = answer;
    return answer;
  }
}



int main(){
  std::map <grid,unsigned long long int> memory;
  std::cout << std::to_string(grd_traveller(grid(1,1),memory))<<"\n"; // Should give 1 and does
  std::cout << std::to_string(grd_traveller(grid(2,3),memory))<<"\n"; // Should give 3 and does
  std::cout << std::to_string(grd_traveller(grid(3,2),memory))<<"\n"; // Should give 3 and does
  std::cout << std::to_string(grd_traveller(grid(3,3),memory))<<"\n"; // Should give 6 and does
  std::map <grid,unsigned long long int> memory2;
  std::cout << grd_traveller(grid(18,18),memory2)<<"\n"; // Should give 2333606220, but doesn't 

}

起初我认为这可能是内存问题，所以我将所有内容都增加到 unsigned long long int 但这并没有解决它。更奇怪的是，对于 18 x 18 网格，如果我使用第一张地图memory或第二张地图，我会得到不同的答案memory2。这很奇怪，我不知道是什么导致了这种行为。有没有人有任何想法？

标签： c++dynamic-programming

解决方案

问题在于您的比较运算符重载：

x + y < rhs.x+rhs.y

这个检查是不够的，因为它只是比较坐标的总和。您应该编写一个按特定顺序检查坐标的代码：

x < rhs.x || x == rhs.x && y < rhs.y

否则，例如，坐标为 (1, 5) 和 (2, 4) 的网格被std::map容器认为是相等的，因为1 + 5 == 2 + 4.

推荐阅读