I have been learning algorithms and trying to solve problems and now I have the following problem:
In a 4x4 matrix, and it contains fields with height. There is a start field with given height also the maximum height a field can have. To be able to traverse from on field to another the height of the current field must be higher or equal to the field we want to go.
There are also unmarked fields with no height assigned to them, meaning we can change it.
The goal is to traverse all the fields with given height by changing the height of the unmarked fields
?. For a solution to count as valid all given
? have to have an assigned height.
I think this will need brute-forcing all the possible combinations of the
2 2 xx*x x1?1 x?1x xxxx
The minimum height a field can have is 0.
The first digit represents the height of the
* and the second, the maximum height a field can have. So the
* represents the start point and has height 2 (for this case we have 2 as maximum height), from there we need to go to the other fields with numbers, by changing the value of the
? fields. We need to find how many variations are valid.
In this case there are : 6. Because the
? on 3rd row does not matter if it gets traversed or not so here are the solutions:
xx*x xx*x xx*x xx*x xx*x xx*x x121 x121 x121 x111 x111 x111 x21x x11x x01x x21x x11x x01x xxxx xxxx xxxx xxxx xxxx xxxx
The nodes that matter have been traversed in both cases. We use Breadth First search to traverse all the nodes. The
? in the 3rd row is not traversed in some of the cases because this field is not in the group of the target fields and its height does not affect reaching any of the target fields.