The problem is finite so, sure, there is an algorithm.
A non-deterministic algorithm can solve the problem easily by guessing the correct moves and then verifying that they work. This algorithm can be determinized by using for example backtracking search.
If you want to reduce the extra tiles (taller grass and concrete) to standard grass, you can go about it like this:
- Every continuous block of concrete is first reduced into a single graph vertex, and then the vertex is removed, because the concrete block areas are actually just a way to move around to reach other tiles.
- Every taller grass tile is replaced with two vertices that are connected to the original neighbors, but not to each other.
Example: G = grass, T = tall grass, C = concrete
G G T
G C T
C C G
Consider it as a graph:
Now transform the concrete blocks away. First shrink them to one (as they're all connected):
Then remove the vertex, connecting "through" it:
Then expand the tall grass tiles, connecting the copies to the same nodes as the originals.
Then replace T, T' with G. You have now a graph that is no longer rectangular grid but it only contains grass nodes.
The transformed problem can be solved if and only if the original one can be solved, and you can transform a solution of the transformed problem into a solution of the original one.