求解[10,10]迷宫的递归算法。我不知道该怎么办算法请帮忙 [英] Recursive algorithm to solve [10,10] maze. I don't know what to do for the algorithm Please Help

问题描述

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace chapterOneAssigment12
{
    class Program
    {
        // Declare array

        char[,] grid = new char[10, 10];               
             
        static void Main(string[] args)
        {
            // Open file

            StreamReader input = new StreamReader("maze.txt");         
                    
            // Char Variable

            char value;

            // Junk String

            string junk;

            // Declare array

            char[,] grid = new char[10, 10];
            
            
            // Algorithm To read in maze

            for (int row = 0; row < 10; row++)
            {
                for (int column = 0; column < 10; column++)
                {
                    value = (char)input.Read();
                    grid[row, column] = value;
                }

                // Dump extra characters 

                junk = input.ReadLine();
            }
            
            input.Close();

            // Other Algorithm To read in maze  

            for (int row1 = 0; row1 < 10; row1++)
            {
                for (int column1 = 0; column1 < 10; column1++)
                {
                    Console.Write(grid[row1, column1]);
                }
                
                Console.WriteLine("");
            }

            MazeSolve(1, 1);    
            
            // Display 

            StreamWriter output = new StreamWriter("maze.out");  
          
            // Call the solve method

            
        }

        // Exit Found Method To Find the exit

        public static void MazeSolve( int row, int column)
        {  
            // Declare boolean 

            bool exitFound;

            exitFound = false;

            if (row == 1)
            {
                exitFound = true;
            }
            else if (row == 9)
            {
                exitFound = true;
            }
            else if (column == 1)
            {
                exitFound = true;
            }
            else if (column == 9)
            {
                exitFound = true;
            }
            else
            {
                if (!exitFound && )
                {
                    
                }
                if (!exitFound &&)
                {
                }
                if (!exitFound &&)
                {
                }
                if (!exitFound &&)
                {
                }
            }

            if (exitFound == true)
            {

                
            }

        }


    } 
}

推荐答案

有很多你可能想要处理的事情irst：最重要的是你的 Main 方法中的 grid 的本地声明会掩盖你在外面声明的类级别版本它。

由于方法内的版本不适用于 Main 以外的方法，例如 MazeSolve ，这意味着你在Main做的事情几乎无关紧要......：笑：



摆脱里面的那个，或者把它作为参数传递到了MazeSolve方法。



在解决迷宫时，有很多方法可以做到：http://en.wikipedia.org/wiki/Maze_solving_algorithm [ ^ ] - 有些人比其他人好。



递归是编码它的一种方式 - 而不是一个坏的方法，因为它让你备份并尝试另一条路线，如果这不起作用。

所以， FindTheWayOut方法需要传递一个单元格引用（起始点），以及它不能进入​​的方向（你输入的方式，以防止你以你进入的方式循环）并返回一个描述路线，或者没有这种路线，如果它找不到它。

在方法中，你可以通过常规依次尝试每个可以离开牢房的方向。如果其中一个呼叫成功，则在备份时传递路由。如果没有尝试下一个方向。如果没有方向可行，则返回没有路线并退出。



尝试在较小的网格上开始（2x2只有一个方式和一个出路很简单）看看调试器中发生了什么事情，然后再使用实际的墙壁来处理更复杂的迷宫！



如果你仍然不确定，那试试吧在纸面上 - 这应该给你一个更好的主意。

There are a number of things you might want to deal with first: the most significant being that the local declaration of grid inside your Main method masks the class level version you declare outside it.
Since the version inside the method will not be available to methods outside Main such as MazeSolve, that means whatever you do in Main is pretty much irrelevant... :laugh:

Get rid of the one inside, or pass it as a parameter to the MazeSolve method.

When it comes to solving a maze, there are a number of ways to do it: http://en.wikipedia.org/wiki/Maze_solving_algorithm[^] - some are better than others.

Recursion is one way to code it - and not a bad one, because it lets you "back up" and try another route if this doesn't work.
So, the FindTheWayOut method needs to be passed a cell reference (the start point), and a direction it can't go in (the way you entered, to prevent you looping back out the way you came in) and to return a value which describes the route, or "no route this way" if it can't find it.
Inside the method, you try each direction in turn by the routine for each of the possible directions you can leave the cell. If one of the calls succeeds, pass the route on back up. If it doesn't try the next direction. If no direction works, pass back "no route this way" and exit.

Try it on a smaller grid to start with (2x2 with just a way in and a way out is simple) and see what happens in the debugger before you work up to more complex mazes with actual walls!

If you still aren't sure, try it on paper first - that should give you a better idea.

你的代码在组织，易读性等方面存在一些问题。首先，当你声明exitFound变量时，你做了声明和后来的任务，我不明白为什么。此外，我不明白为什么你认为在第一行意味着你找到了退出。您不必使用递归，因为您必须知道每个递归算法都有其迭代版本，反之亦然。尽管递归版本可以是优雅的并且是短编码的，但迭代版本可能更容易构建。在你的问题中，递归方法在每个可行的方向上调用自身，直到它到达退出，这是停止标准。

There are some problems with your code in terms of organization, legibility, etc. First, when you declare the exitFound variable you made the declaration and later the assignment, I don't see why. Also I don't see why you consider that being in the first row means that you've found the exit. You don't have to use recursion, as you must know every recursive algorithm has its iterative version and viceversa. Even though the recursive version could be elegant and short-coded the iterative version might be easier to build. In your problem the recursive method makes a call to itself in every feasible direction, until it reaches the exit, which is the stopping criteria.

这篇关于求解[10,10]迷宫的递归算法。我不知道该怎么办算法请帮忙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！