C++ Maze Program 求教

中國日本

Question: Write a program to find a path in a maze using recursion. A maze is an n by n square of cells each of which is either blocked or clear. Your program starts at the top left corner and tries to find a path (of clear cells) leading to the lower right corner. Each move is either horizontally (left or right) or vertically (up or down) but never diagonally. Note that a path may not exist.
The maze is represented by a two-dimensional bool array, where true means blocked and false means clear. Your program should ask the user to input the size of the maze followed by the maze row by row. Your program should also maintain another char array to record the path found (if there is one) and print it out at the end of processing. Your program should work for mazes of sizes between 4 and 20.
One simple way to find a path is at each step: try moving along one of the allowable directions and try another direction if that one fails. If no possible path can be found, fall back to the previous step and try another path. Note that a move is not allowed if the cell to be moved into is either blocked or that it is outside of the maze. Note also that our simple method may loop in “circles” inside the maze and needs to be augmented so that it will not get into an infinite loop.


My Program:
#include<iostream>

using namespace std;



int main(){
       
        int input=0;
       
        for (;input<4 || input>20;){
        cout << "Please input size of maze (a number between 4 and 20 is expected) -> ";
        cin >> input;
               
        if (input<4 || input>20)
        cout << "**Error** maze size is not in range!\n";
        }

       
        int maze[input-1][input-1];
       
        cout << "Please input contents of maze row by row. 1 for barrier and 0 for free passage.\n\n";
       
        for (int i=0;i<input;i++){
                for (int n=0;n<input;n++){
                cin >> maze[i][n];
                }
        }
       
        if ((maze[0][1]==1 && maze[1][0]==1)||(maze[0][0]==1)){
        cout << "**Error** entrance to maze is blocked!\n";
        return 0;
        }
       
        int h = input -1;
        int v = input -1;
       

       
        for (long t=0;(h>0 || v>0)&&(t<input*input);t++){
                if (maze[h-1][v] == 0)
                h=h-1;
                else if (maze[h][v-1] == 0)
                v=v-1;
                else if ((h<input-1)&& maze[h][v] == 0)
                h=h+1;
                else if ((v<input-1)&& maze[h][v] == 0)
                v=v+1;
        }

       
        if (v==0 && h==0)
        cout << "The maze and the path:\n";
        else cout << "**Warning** no path from entrance to exit!\n" << "The maze and the path:\n";
       
        cout << "+";
        for (int q=0;q<input;q++)
        cout << "-";
        cout << "+\n";
       
        //HERE THE FUNCTION OF PRINTING THE MAZE
       
        cout << "+";
        for (int q=0;q<input;q++)
        cout << "-";
        cout << "+\n";
}

求高手教路, 應該點check有冇path? Thanks

Jackass_TMxCK

Do you know what is Stack?

中國日本

回覆 2# Jackass_TMxCK

I haven't learnt this.
May I know what is stack in C++?

Jackass_TMxCK

回覆  Jackass_TMxCK

I haven't learnt this.
May I know what is stack in C++?
中國日本 發表於 5/11/2014 02:24 AM

Stack 係一個Data Structure

Try moving along one of the allowable directions and try another direction if that one fails. If no possible path can be found, fall back to the previous step and try another path.

呢個方法同Stack generate/ solve maze一樣，點確定有你未真係做以上ge functions再行一次個迷宮，正確無誤ge code行一次佢真係係頭去到終點ge未為之有path
如果每個cell都行過都未出到去，咁未係姐係唔會有path

一個array記成個maze有邊幾格行過，一個就記solution
solution個array每行一格就push最新行個格，退就pop。pop時就check下週圍四格有無未行過，有就是但行一格不停咁去。等到你Instruction入面所講咁

ip4368

回覆 3# 中國日本

stack is not particular for c++, as Jack said, it is a data structure, you should learn more data structure as you can. they are helpful. beside stack, queue is also a useful data structure. in fact there are a lot of computer program that base on those data structure. for example, recursion have to concept of stack.

hihihi123hk

Question: Write a program to find a path in a maze using recursion. A maze is an n by n square of ce ...
中國日本 發表於 2014-11-5 01:17

    教左點起class 未？

中國日本

回覆 6# hihihi123hk

未教@@
只係教到functions 同 Array

中國日本

回覆 7# toylet

google揾到好多maze program, 但係只係睇得明好少