Jackass_TMxCK

Try to read this:
skhui2005 發表於 5/11/2014 09:12 PM

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


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

中國日本

回覆 20# Jackass_TMxCK

HKU Computer Programming
target Business, Science, QFin students

中國日本

回覆 21# Jackass_TMxCK

thanks, will read is asap

hihihi123hk

回覆  Jackass_TMxCK

HKU Computer Programming
target Business, Science, QFin students
中國日本 發表於 2014-11-6 00:02

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

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

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

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

https://github.com/gaplo917/C_Simple_Maze

hihihi123hk

回覆 25# toylet

Low tech 既 識數只係有啲幫助

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

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

smoke_cheese

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

回覆 29# smoke_cheese

"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"


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 . => the recursion is always return the shortest path.