jjzjj

c++ - 迷宫解算器记录回溯路径

coder 2024-02-23 原文

我已经让我的迷宫解算器程序开始工作，但它似乎在它输出的最终解决方案路径中包括回溯空间(它去的地方撞到墙上，所以它不得不掉头)。这是一个例子:

如何在我当前的以下实现中防止这种情况:

int dir = 4;

bool visited[Max_Maze][Max_Maze][dir];


for (row = 0; row < size; ++ row)
{
  for (col = 0; col < size; ++ col)
  {
    for (dir = 0; dir < 4; ++ dir)
    {
      visited[row][col][dir]=false;
    }
  }
}

bool notSolved = true;
int path = 0;
row = 0;
col = 0;

rowStack.push(row);
colStack.push(col);

while (notSolved)
{

  //from perspective of person looking at maze on screen
  if (((row-1)>=0)&&(maze[row - 1][col] == 0)&&(visited[row][col][0]==false))
  {
    // if that space is not out of bounds and if you can go up
    // and you have not gone in that direction yet, go up
    visited[row][col][0] = true; 
    row--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col+1)<size)&&(maze[row][col + 1] == 0)&&(visited[row][col][1]==false))
  {
    //else if you can go right etc., go right
    visited[row][col][1] = true;
    col++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((row+1)<size)&&(maze[row + 1][col] == 0)&&(visited[row][col][2]==false))
  {
    //else if you can go down etc., go down
    visited[row][col][2] = true;
    row++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col-1)>=0)&&(maze[row][col - 1] == 0)&&(visited[row][col][3]==false))
  {
    //else if you can go left etc., go left
    visited[row][col][3] = true;
    col--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else
  {
    //if stuck
    if (path == 0)
    {
      cout << "No Solution Path" << endl;
      notSolved = false;
    }
    else
    {
      rowStack.pop();
      colStack.pop();
      row = rowStack.top();
      col = colStack.top();
      path--;
    }
  }

  if((maze[row][col] == 0) && (row == (size - 1) && col == (size - 1)))
  {
    //if we reached an exit
    cout << "Solution Path:(in reverse)" << endl;
    for (int i = 0; i <= path; i++)
    {
      cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
      rowStack.pop();
      colStack.pop();
    }
    notSolved = false;
  }
}

需要简单的修复还是全面重组？

最佳答案

当求解器直接进入那个死胡同时，它会记录它“直接从 (R, C) 访问”，因为您访问的数组是三维的。但它从不记录它“从 (R, C + 1) 访问左”。所以它认为移动到相同的 position 两次是可以的，只要它不做两次完全相同的移动(它没有，因为它在回溯时向左移动，而不是向右移动).

如果您将 visited 更改为二维数组并且仅记录位置，而不是移动，看起来它会正常工作。然后你之前访问过的每个方 block 都会阻止进一步的移动，但这没关系，因为如果正确的解决方案需要回到那个方 block ，你最终会遇到足够多的 else 情况以弹回到它，并且从那里三个必须是 never-参观广场探索。

关于c++ - 迷宫解算器记录回溯路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8332133/

amp43colrowc++maze

有关c++ - 迷宫解算器记录回溯路径的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - Sinatra:运行 rspec 测试时记录噪音 - 2

    Sinatra新手；我正在运行一些rspec测试，但在日志中收到了一堆不需要的噪音。如何消除日志中过多的噪音？我仔细检查了环境是否设置为:test，这意味着记录器级别应设置为WARN而不是DEBUG。spec_helper:require"./app"require"sinatra"require"rspec"require"rack/test"require"database_cleaner"require"factory_girl"set:environment,:testFactoryGirl.definition_file_paths=%w{./factories./test/

  3. ruby-on-rails - Rails 5 Active Record 记录无效错误 - 2

    我有两个Rails模型，即Invoice和Invoice_details。一个Invoice_details属于Invoice，一个Invoice有多个Invoice_details。我无法使用accepts_nested_attributes_forinInvoice通过Invoice模型保存Invoice_details。我收到以下错误:(0.2ms)BEGIN(0.2ms)ROLLBACKCompleted422UnprocessableEntityin25ms(ActiveRecord:4.0ms)ActiveRecord::RecordInvalid(Validationfa

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  6. ruby-on-rails - 事件记录 : Select max of limit - 2

    我正在尝试将以下SQL查询转换为ActiveRecord，它正在融化我的大脑。deletefromtablewhereid有什么想法吗？我想做的是限制表中的行数。所以，我想删除少于最近10个条目的所有内容。编辑:通过结合以下几个答案找到了解决方案。Temperature.where('id这给我留下了最新的10个条目。 最佳答案 从您的SQL来看，您似乎想要从表中删除前10条记录。我相信到目前为止的大多数答案都会如此。这里有两个额外的选择:基于MurifoX的版本:Table.where(:id=>Table.order(:id).

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  9. Ruby 守护进程导致 ActiveRecord 记录器 IOError - 2

    我目前正在用Ruby编写一个项目，它使用ActiveRecordgem进行数据库交互，我正在尝试使用ActiveRecord::Base.logger记录所有数据库事件具有以下代码的属性ActiveRecord::Base.logger=Logger.new(File.open('logs/database.log','a'))这适用于迁移等(出于某种原因似乎需要启用日志记录，因为它在禁用时会出现NilClass错误)但是当我尝试运行包含调用ActiveRecord对象的线程守护程序的项目时脚本失败并出现以下错误/System/Library/Frameworks/Ruby.frame

  10. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

随机推荐