Let's consider dominoes as edges and values written on dominoes as 2 vertexes. In this case all you have to do is to find Eulerian path, that can be done in O(n+m).

Maybe this will be helpful. ;)