我对网格旅行者问题的实现只适用于小网格

Question

我正在 38:39 尝试这个问题，进入这个免费的代码训练营视频：https://youtu.be/oBt53YbR9Kk?t=2361

问题如下：

Say that you are a traveller on a 2D grid. You begin in the top left corner and and your goal is to travel to the bottom right corner. You may only move down or right.

In how many ways can you travel to the to the goal on a grid with dimensions m*n

Write a function GridTraveller(m,n) that calculates this.

除了 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，我会得到不同的答案。这很奇怪，我不知道是什么导致了这种行为。有人有什么想法吗？

Answer 1

问题出在你的比较运算符重载上：

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.

我对网格旅行者问题的实现只适用于小网格

My implementation of the grid traveller problem only works for small grids

c++

dynamic-programming