Jump to content

Maze / Graph


dawoodr

Recommended Posts

Hello!

 

Well, there is a problem which I sort of don't know how to solve. Given a matrix starting at top left corner how do you find all possible paths given x steps.

 

Example 3x3 matrix and you have 5 steps.

 

7 2 9

2 7 5

6 1 9

 

So now starting at 7 you need to find all possible paths/all possible sums using only 5 steps. You can move up, down, left right. Not diagonally or jump between numbers. You can't visit the numbers you already visited twice.

 

I am working in C++.

 

Regards!

Link to comment
Share on other sites

Traversal via conditional statements would work.

 

Another option might be to create a list of all the options and refine your results from there.

 

 

 

 

A B C

D E F

G H I

 

Find all possible combinations of A-I without repeats, remove all those over 5 letters long, remove all those which don't start with A, remove all those without B or D as the second letter, remove all those without C,E,G as the third letter, etc.

 

at the end map your results to your grid and sum the results.

 

 

 

Looks like best bet would be to look up self avoiding walks. May be able to find a better solution out there.

Link to comment
Share on other sites

8

 

at the end map your results to your grid and sum the results.

 

Plus eliminate duplicates.

<?php
$a="7";$b="2";$c="9";
$d="2";$e="7";$f="5";
$g="6";$h="1";$i="9";
echo strlen(preg_replace('/\s+/', '', str_replace(",","",implode(',',array_unique(explode(',', "
{$a}{$b}{$c}{$f}{$e},
{$a}{$b}{$e}{$f}{$i},
{$a}{$b}{$e}{$h}{$g},
{$a}{$b}{$e}{$h}{$i},
{$a}{$b}{$e}{$f}{$c},
{$a}{$b}{$e}{$d}{$g},
{$a}{$d}{$g}{$h}{$i},
{$a}{$d}{$g}{$h}{$e},
{$a}{$d}{$e}{$h}{$g},
{$a}{$d}{$e}{$f}{$i},
{$a}{$d}{$e}{$f}{$c},
{$a}{$d}{$e}{$b}{$c}"))))))/5;
?>

There is a total of three possible sequences the one above and

for a side

bcfed
bcfeh
bcfih
badef
badeh
badhi
befih
bedgh
behgd
behif

 

for the middle
ebadg
ebcfi
ehifc
ehgda
efcba
efcih
edabc
edghi

Edited by fiveworlds
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.