CLS
OPTION BASE 1

'Read in Map.
'The format is 0 is impassible while 1 is passable.
READ MapX%, MapY%
READ StrX%, StrY%, EndX%, EndY%
DIM Map%(MapX%, MapY%)

FOR I% = 1 TO MapY%
  FOR z% = 1 TO MapX%
    READ Map%(z%, I%)
  NEXT z%
NEXT I%

DIM Visited%(MapX%, MapY%)

'Allocate the stack
DIM X%(MapX% * MapY%), Y%(MapX% * MapY%)
SP% = 0

'Push the initial position on the stack
SP% = SP% + 1
X%(SP%) = StrX%: Y%(SP%) = StrY%
Visited%(StrX%, StrY%) = 1

DO WHILE SP% <> 0
  'Temporary reference current position
  CurX% = X%(SP%): CurY% = Y%(SP%)

  'Are we at the end?
  IF CurX% = EndX% AND CurY% = EndY% THEN EXIT DO

  'Try going right
  IF Map%(CurX% + 1, CurY%) AND NOT Visited%(CurX% + 1, CurY%) THEN
    SP% = SP% + 1
    X%(SP%) = CurX% + 1: Y%(SP%) = CurY%
    Visited%(CurX% + 1, CurY%) = 1
  'Try going left
  ELSEIF Map%(CurX% - 1, CurY%) AND NOT Visited%(CurX% - 1, CurY%) THEN
    SP% = SP% + 1
    X%(SP%) = CurX% - 1: Y%(SP%) = CurY%
    Visited%(CurX% - 1, CurY%) = 1
  'Try going down
  ELSEIF Map%(CurX%, CurY% + 1) AND NOT Visited%(CurX%, CurY% + 1) THEN
    SP% = SP% + 1
    X%(SP%) = CurX%: Y%(SP%) = CurY% + 1
    Visited%(CurX%, CurY% + 1) = 1
  'Try going up
  ELSEIF Map%(CurX%, CurY% - 1) AND NOT Visited%(CurX%, CurY% - 1) THEN
    SP% = SP% + 1
    X%(SP%) = CurX%: Y%(SP%) = CurY% - 1
    Visited%(CurX%, CurY% - 1) = 1
  'Dead end
  ELSE
    SP% = SP% - 1
  END IF
LOOP

'Display Map
FOR I% = 1 TO MapY%
  FOR z% = 1 TO MapX%
    IF Map%(z%, I%) = 1 THEN PRINT " ";  ELSE PRINT "#";
  NEXT z%
  PRINT
NEXT I%
LOCATE StrY%, StrX%: PRINT "S"
LOCATE EndY%, EndX%: PRINT "E"

'Failure?
IF SP% = 0 THEN LOCATE MapY% + 1: PRINT "No Possible Path": END

'Show path
COLOR 14
FOR I% = 3 TO SP%
  DiffX% = X%(I%) - X%(I% - 1)
  DiffY% = Y%(I%) - Y%(I% - 1)
  
  IF DiffX% = 1 THEN
    c$ = ">"
  ELSEIF DiffX% = -1 THEN
    c$ = "<"
  ELSEIF DiffY% = 1 THEN
    c$ = "v"
  ELSE
    c$ = ">"
  END IF
  LOCATE Y%(I% - 1), X%(I% - 1): PRINT c$;
NEXT I%

'Map X, Map Y
DATA 10,10
'Map StartX, StartY, EndX, EndY
DATA 2,2,9,9
DATA 0,0,0,0,0,0,0,0,0,0
DATA 0,1,1,1,1,1,1,0,1,0
DATA 0,1,0,0,0,1,1,0,1,0
DATA 0,1,1,1,1,1,1,1,1,0
DATA 0,0,1,0,1,0,1,0,1,0
DATA 0,0,1,0,1,1,1,0,1,0
DATA 0,1,1,0,0,1,1,1,1,0
DATA 0,1,0,1,0,0,1,0,0,0
DATA 0,1,1,1,1,0,1,1,1,0
DATA 0,0,0,0,0,0,0,0,0,0