標題: C++ Maze Program 求教 [打印本頁]

---

作者: 中國日本    時間: 2014-11-5 01:17     標題: 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    時間: 2014-11-5 02:05

Do you know what is Stack?

---

作者: 中國日本    時間: 2014-11-5 02:24

回覆 2# Jackass_TMxCK

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

---

作者: Jackass_TMxCK    時間: 2014-11-5 10:12



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    時間: 2014-11-5 12:01

回覆 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    時間: 2014-11-5 20:02




    教左點起class 未？

---

作者: toylet    時間: 2014-11-5 20:23

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: 中國日本    時間: 2014-11-5 20:36

回覆 6# hihihi123hk

未教@@
只係教到functions 同 Array

---

作者: 中國日本    時間: 2014-11-5 20:37

回覆 7# toylet

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

---

作者: toylet    時間: 2014-11-5 20:42

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: 中國日本    時間: 2014-11-5 20:50

回覆 10# toylet

係game programming..
呢幾日不斷睇緊啲
係試咗幾日都冇乜頭緒先上嚟問下

---

作者: toylet    時間: 2014-11-5 20:53

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: toylet    時間: 2014-11-5 21:00

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: 中國日本    時間: 2014-11-5 21:03

回覆 12# toylet

應該唔講呢啲topic
始終係第一個programming course

---

作者: toylet    時間: 2014-11-5 21:08

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: skhui2005    時間: 2014-11-5 21:12

Try to read this: Maze solver

---

作者: Jackass_TMxCK    時間: 2014-11-5 23:14



Game Programming未學OOP未學Data Structure Software Design = onj wor?

---

作者: Jackass_TMxCK    時間: 2014-11-5 23:16




    2014年了，做game無咩人會學點寫3D engine


做game又好咩都好唔好學low level野，學點快手develope野好重要，除非你想叉雞飯都唔夠錢買

---

作者: Jackass_TMxCK    時間: 2014-11-5 23:19

做Game要學AI、Data Structure、Software design/ Engineering，其他野用framework解決，去鑽computer graphic ge theory再自己做game engine真係好脫節唔知呢個世界做緊嚀

---

作者: Jackass_TMxCK    時間: 2014-11-5 23:22




    咩學院咁巴閉一黎就做maze？我Year 2 讀Data Structure final project先做maze，當然程度唔同。

UST Year 1聽過係做有AI ge 過三關

---

作者: Jackass_TMxCK    時間: 2014-11-5 23:23




    http://www.jamisbuck.org/presentations/rubyconf2011/index.html


學做Maze睇呢篇好詳細，當然要有底先睇得明

---

作者: 中國日本    時間: 2014-11-6 00:02

回覆 20# Jackass_TMxCK

HKU Computer Programming
target Business, Science, QFin students

---

作者: 中國日本    時間: 2014-11-6 00:06

回覆 21# Jackass_TMxCK

thanks, will read is asap

---

作者: toylet    時間: 2014-11-6 00:24

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: toylet    時間: 2014-11-6 00:27

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: hihihi123hk    時間: 2014-11-6 02:27



好耐無寫過 C++, 係咁睇番啲 C＋＋Library , 搞左 粒幾鐘先 搞到壇野出黎， 你可以參考下

呢個係 好 初級 純用 Dynamic array ＋ Recursion ，應該 岩你程度，

P.S. 呢個唔係最好及最快既寫法

想學點做 recursion , 可以試下 delete 左 // TODO :   下面既 code 睇下 寫唔寫得番出黎

https://github.com/gaplo917/C_Simple_Maze

---

作者: hihihi123hk    時間: 2014-11-6 14:42

回覆 25# toylet

Low tech 既 識數只係有啲幫助

Hight tech 既 講緊 只要條algorithm 快1% 都會改黎用

例如每秒 幾億個Request , 1% 差幾遠

---

作者: toylet    時間: 2014-11-6 18:55

提示: 作者被禁止或刪除 內容自動屏蔽

---

作者: smoke_cheese    時間: 2014-11-7 12:16

本帖最後由 smoke_cheese 於 2014-11-7 12:22 編輯

Actually the question already told you how to solve it.

"Write a program to find a path in a maze using recursion."
"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."

The top left (start) cell is (0,0) and the bottom right (exit) cell is (n,n).

You want to write a function to check if cell (x,y) can reach the exit.

You know:

Check(x,y) is false if cell (x,y) is blocked.
Check(n,n) is true if cell (n,n) is open.

"moving along one of the allowable directions"
"Each move is either horizontally (left or right) or vertically (up or down) but never diagonally."

Check(x,y) is true if cell (x,y) is open and (
  Check(x-1,y) is true or
  Check(x+1,y) is true or
  Check(x,y-1) is true or
  Check(x,y+1) is true )

So you write Check(x,y) to call those four functions above recursively.

Then you can just call Check(0,0) from your main program.  If Check(0,0) is true then there is a solution to the maze.

Notes:

1. You also don't want to go back the direction you came so you also need to pass the direction you're coming from to Check(x,y), or you'll have to mark cells you've visited and not visit them twice (this would solve the problem of going in circles mentioned in the question as well).

2. The question also ask you to record the path taken.  So you pass the current path you have to Check(x,y) also and append the new direction to the path depending on which of the four direction returns true, then return the new path to the caller.

---

作者: hihihi123hk    時間: 2014-11-7 20:50

本帖最後由 hihihi123hk 於 2014-11-7 21:00 編輯

回覆 29# smoke_cheese

&quot;The question also ask you to record the path taken.  So you pass the current path you have to Check(x,y) also and append the new direction to the path depending on which of the four direction returns true, then return the new path to the caller&quot;


To clarify,
C++ does not support mixed return type

if the recursion return Path( Suppose it is a class), it should be return an array of Path (Every possible Path ). And merge the array on every recursion

if the recursion return Boolean(true/false), it is good that the recursion will end when the shortest path is found. we can save the path at at the recursion break point.
i.e
return R(x+1,y)|| R(x,y+1) || R(x-1,y)|| R(x,y-1);

if one of the function is true, the function is supposed to stop . =&gt; the recursion is always return the shortest path.