Help develop Alphys' newest puzzle!

Question

Alphys, the Underground's Royal Scientist, has finished a prototype for a new puzzle. However, she can't seem to find anyone willing to test it.

The rules of her puzzle are as follows:

The goal is to get to the right side, starting from the centermost tile on the left side. For puzzles with even-numbered heights, start on the lower of the two center tiles. (Examples: In a zero-indexed 4x4 array, the starting position would be [2,0] - row 2, column 0. In a zero-indexed 5x5 array the starting position would be [2,0] - row 2, column 0.)

Each colored tile has its own "sadistic" function:

• Pink and green tiles (represented as "P" and "G") do nothing
• Red and yellow tiles ("R", "Y") are impassable.
• Orange tiles ("O") make the player smell like oranges
• Purple tiles ("U") force the player to the next tile in the direction they are facing and make them smell like lemons
• Blue tiles ("B") are passable as long as the player does not smell like oranges.

To clarify the flavor mechanic, a player's smell will persist indefinitely or until overridden by a different-smelling tile, i.e. if a player steps on an orange tile they will smell like oranges until they step on a purple tile.

Additionally, a yellow tile placed vertically or horizontally adjacent to a blue tile will cause the blue tile to become impassable as well.

Your task is to write a program or function that accepts a 2-dimensional character array (or 1D string array, or some other valid format) representing the puzzle's layout as input and outputs both the original puzzle and the solved puzzle, with asterisks or some other character showing the correct path. Assume that the given puzzle is solveable.

Use this puzzle as an example:

BGYBG
PGPBG
PUBPB
OUGYB
PPOPP

Your program would output:

BGYBG
PGPBG
PUBPB
OUGYB
PPOPP

BGYBG
PGPBG
*****
OUGYB
PPOPP

Any puzzle used must be generated using this.

Standard code golf rules apply. Best answers will be the shortest for each language. Answers must contain the language, number of bytes, and three test cases. The first two can be any layout you choose, but the third must be:

RRRR
RPPR
PUOR
RPBP

Answer 1

C 529 bytes

#define M m[y][x]
char**m,*l,i;main(Y,X){for(;scanf("%ms",&l)>0;)(m=realloc(m,Y*8))[Y-1]=l,X=puts(m[Y++-1])-2;puts("");int s(x,y,c,d){(x<0|y<0|y/Y)?:({if(M^'R'&&M^'Y')if(M^'B'||c^2&&!((y&&m[y-1][x]=='Y')|(x&&m[y][x-1]=='Y')|(y<Y-1&&m[y+1][x]=='Y')|(x<X-1&&m[y][x+1]=='Y'))){x^X?:({M='#';return 1;});c=M^'O'?c:2;M^'U'?:({return s(x+(d<4?d-2:0),y+(d>3?d-5:0),1,d)?({M='#';1;}):0;});if(d^1&&s(x+1,y,c,3)||d^4&&s(x,y+1,c,6)||d^6&&s(x,y-1,c,4)||d^3&&s(x-1,y,c,1)){M='#';return 1;}}});return 0;}s(0,--Y/2,0,3);for(;i<Y;)puts(m[i++]);}

We approach the puzzle by stepping first to the right, provided we are not blocked, then trying up, then down and finally back to the left. The search is recursive and once we identify a successful path, we mark the spaces in our matrix and return.

Try it Online

Ungolfed

#include <stdio.h>
#include <malloc.h>
char**m,*l,i;
main(Y,X) {
  for(Y=1;scanf("%ms",&l)>0;Y++)
      m=realloc(m,Y*8),
      m[Y-1]=l,
      X=puts(m[Y-1])-2;
  puts("");
  int step(x,y,c,d,i){
    if(x<0||y<0||y>=Y)return 0;
      if(m[y][x]=='R'||m[y][x]=='Y')return 0;
      if(m[y][x]=='B'&&(c==2||(y&&m[y-1][x]=='Y')||(x&&m[y][x-1]=='Y')
               ||(y<Y-1&&m[y+1][x]=='Y')||(x<X-1&&m[y][x+1]=='Y')))return 0;
      if(x==X){m[y][x]='#';return 1;}
      if(m[y][x]=='O')c=2;
      if(m[y][x]=='U')return step(x+(d<4?d-2:0),y+(d>3?d-5:0),1,d,i+1)?({m[y][x]='#';1;}):0;
      else if((d!=1&&step(x+1,y,c,3,i+1)) ||
    (d!=4&&step(x,y+1,c,6,i+1)) || (d!=6&&step(x,y-1,c,4,i+1)) ||
    (d!=3&&step(x-1,y,c,1,i+1))) {m[y][x]='#';return 1;}
      return 0;
  }
  step(0,--Y/2,0,3,0);
  for(;i<Y;)puts(m[i++]);
}

---

Example Output 1

PYYOPPPP
YRGGRYRG
PGPBYPUR
PYRBOYOG
OBPGYYPP
PRGPOYPO
YPYOUGPP
YGROBRYY
RGRYBBOG

PYY#####
YR##RYRG
###BYPUR
#YRBOYOG
#BPGYYPP
PRGPOYPO
YPYOUGPP
YGROBRYY
RGRYBBOG

Example Output 2

PBYRYPGP
OBRGOOBG
PGPGUROO
PUGORBUG
PUPUUURO
BGGUYPRG
GBOPGGRG
PUPUBUYB
GYOPRPOG

PBYRYPGP
OBRGOOBG
PGPGUROO
PUGORBUG
###UUURO
BG#UYPRG
GB####RG
PUPUB#YB
GYOPR###

Example Output 3

RRRR
RPPR
PUOR
RPBP

RRRR
R##R
###R
R###