Cover positions with snakes of same 'colour'

Imagine a grid where the origin square $(0,0)$ is at the top left of the screen, and positive $x$ is rightwards whereas positive $y$ is downwards. Coloured squares are at various positions on the grid.

In a magical void separate from the grid are multiple snake-like strips of squares, each of a fixed length and a certain colour. Colours may or may not repeat across strips.

Each of our strips can move left, right or forward from the perspective of the head but can obstruct itself. The strips basically move by popping the tail and pushing a new head, as snakes do. They are necessary and sufficient to cover every correspondingly coloured position on the grid without strip overlap.

1. At any one time, you select a single snake from your inventory to control. It appears at $(0,0)$ pointing downwards, and moves are counted after this happens (see Samples below).
2. Whenever you select a new snake, the previous one gets stuck where it is.

Sounds dreadful, doesn’t it? It’s as if you need to plan all your moves…!

What moves will solve the grid?

Input

• A matrix where different colours are represented by differing positive integers, and an uncoloured position is represented by 0.
• Each strip’s ‘colour’; its length; and, since strips may share colours, a unique identifier.

You need only consider grids solvable by the method described in the introduction.

Output

Give the unique identifier of each strip you’re moving, and the sequence of moves it should make:

• You may use any consistent value for up ($-y$ wrt the grid), any consistent value for down ($+y$), any consistent value for left ($-x$ wrt the grid) and any consistent value for right ($+x$).

More than one solution is typically possible. Please choose one.

Possible output types are not limited to associative arrays.

---

In the sample test cases below, for the sake of example only, W, A, S, D represent up, left, down and right respectively. Also for the sake of example only, these rules are followed:

• In the input, the unique identifier for a strip is given first, followed by its ‘colour’, followed by its length.
• In the output, the unique identifier for any strip is followed by the moves for that strip. Consider the sets of moves in their given order.
• Unique identifiers will be letters.

Sample 1

Input — grid

0010000
0000100

Input — strips

a 1 4

Possible output

a DDDS

Result (strip narrowed for clarity): image link

Sample 2

Input — grid

0010000
0200000
0030100
0002020
0000300

Input — strips

a 1 5
b 2 7
c 3 5

Possible output

a DDDDSS
b SDDDSSDD
c SSDDSSDD

Result (strips narrowed for clarity): image link

Sample 3

Input — grid

0000000
0010120
0030000
0102000
0000000
0000310
0000000

Input — strips

a 1 3
b 1 6
c 2 7
d 3 6

Possible output

b DDDDSSDSSS
c SSSSDDDWWWWDDS
d DDSSSSSDD
a DDSASS

Result (strips narrowed for clarity): image link

Sample 4

Input — grid

000000
010000
000020
030000
020040
040100
000300
000000

Input — strips

a 1 11
b 2 8
c 3 6
d 4 9

Possible output

c SSSDDSSSD
d SSSSSDSSDDDWWW
b DDDDSSAAAASSD
a SDDDDDSSAASS

Result (strips narrowed for clarity): image link

---

• code-golf; the shortest code in bytes wins.
• The linked rules apply.
• Please explain your code.
• Please link to Try It Online! or another online demo.

---

Samples credit: Color Strips on Armor Games