In the grid below, a step is legal if it begins in any hexagon and moves to an adjacent hexagon that contains a different letter. Assuming you can start anywhere, compute the total number of distinct, directed paths of 2 legal steps.
I'm not sure of any way to do this without simply bashing it out and counting all the paths. Is there an efficient way to do this?
First tabulate the amount of of $1$-step paths from each node (write it in the node):
Then for the $2$-step paths from a node $x$ add up the amounts of $1$ step paths of each neighboring node (to where you can move from $x$), for example:
Explanation: You can count all the $2$-step paths by considering the first step of the path. It can be to any neighboring tile and then you can continue from that tile with any $1$-step path.
Calculating this for all nodes we get:
Now we add all these up to get the total number of $2$ step paths, which is $110$.
Note: this is equivalent to calculating the powers of the adjacency matrix of the graph connected to this problem (the nodes are the tiles and there is an directed edge between nodes when you can move from one to the other). You can continue in the same manner for longer paths ($3$ steps and so on) by doing the similar summation for the previously gotten values.