Maze / Graph

[dawoodr]

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!

[Endy0816]

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.

[fiveworlds]

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 November 25, 2014 by fiveworlds