Matrix Shortest Path

Question

I can move left, right, up, down - no diagonal movement is allowed.
Can only travel to cells that contain 1s, not 0s.
Start in upper left cell (0,0)
End in lower right cell (2,3)
Last cell is undefined, should be (2,3).

let visited = [[false, false, false, false],
[false, false, false, false],
[false, false, false, false]]

function shortestPath(arr, c, r) {
    if (arr.length === c + 1 && arr[0].length === r + 1) {
        if (arr[c][r] === 1) {
            return true;
        }
        else { return false }
    }

    if (c === arr.length || r === arr[0].length || c < 0 || r < 0) { return }
    console.log(r, c)
    if (arr[c][r] === 0) { return }
    if (visited[c][r]) { return }
    visited[c][r] = true

    shortestPath(arr, c, r + 1)
    shortestPath(arr, c + 1, r)
    shortestPath(arr, c, r - 1)
    shortestPath(arr, c - 1, r)

}
let a = [[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 1, 1, 1]]
console.log(shortestPath(a, 0, 0))

Output:
0 0
1 0
2 0
3 0
2 1
1 0
1 1
2 1
1 2
2 2
1 2
2 1
0 2
1 2
0 1
1 1
0 2
0 0
1 1
0 1
1 0
0 0
0 1
undefined

Answer 1

There you go: https://jsfiddle.net/vanowm/j0dxqy7h/

function shortestPath(arr, start, end)
{
  arr = arr.map(a => [...a]); //clone matrix, so we can re-use it by updating which coordinates we've visited
  if (!start)
    start = [0, 0];

  if (!end)
    end = [arr[0].length-1, arr.length-1];

  arr[start[1]][start[0]] = 0; //set start position as unavailable
  const paths = [[start]];
  while (paths.length)
  {
    const path = paths.shift(), //remove first path out of all paths (we'll add it back to the end if it's not a dead end)
          cur = path[path.length-1], //get last coordinates from the path
          next = [ //next coordinates from current position
            [cur[0], cur[1] + 1],
            [cur[0] + 1, cur[1]],
            [cur[0], cur[1] - 1],
            [cur[0] - 1, cur[1]],
          ];

    for (let i = 0, pos; i < next.length; i++)
    {
      pos = next[i];
      if (pos[0] == end[0] && pos[1] == end[1])
        return path.concat([end]); //found end position

      if (pos[0] < 0 || pos[0] >= arr[0].length || //check boundaries for x
          pos[1] < 0 || pos[1] >= arr.length || //check boundaries for y
          !arr[pos[1]][pos[0]]) //position available?
      {
        continue;
      }

      arr[pos[1]][pos[0]] = 0; //mark position unavailable
      paths.push(path.concat([pos])); //add position to the path
    }
  }
  return [start]; //return start coordinates if no path found
}


showMatrix([
  [1, 1, 1, 0],
  [1, 1, 0, 1],
  [1, 1, 1, 1]
]);


custom([
  [1,1,0,1,1,1,1,0],
  [1,0,1,1,0,0,1,1],
  [1,0,1,0,1,1,0,1],
  [1,0,1,1,0,1,1,1],
  [1,0,0,1,0,1,0,0],
  [1,1,0,1,0,1,1,1],
  [1,0,1,1,1,0,0,1],
  [1,1,0,0,1,0,1,1],
  [0,1,1,1,1,0,1,1]
], [1,0],[6,7]);

function showMatrix(matrix, start, end, _box)
{

  if (!start || start[0] >= matrix[0].length || start[1] >= matrix.length)
    start = [0, 0];

  if (!end || end[0] >= matrix[0].length || end[1] >= matrix.length)
    end = [matrix[0].length-1, matrix.length-1];

  const path = shortestPath(matrix, start, end);
console.log("matrix:", JSON.stringify(matrix));
console.log("path:", path.join("|"));

  path.forEach(b => matrix[b[1]][b[0]] = 2); //merge path into matrix
  matrix[start[1]][start[0]] = 3; //identify start
  matrix[end[1]][end[0]] = 4; //identify end
  let div = document.createElement("div");
  const box = _box || div.cloneNode();
  box.className = "matrix";
  box.innerHTML = "";
  box.style.gridTemplateColumns = "1fr ".repeat(matrix[0].length);
  const pathPos = {};
  path.forEach((a,i) => pathPos[a.join("x")] = i);
  matrix.forEach((r, y) => r.forEach((t, x) =>
  {
    div = div.cloneNode(false);
    div.className = "t" + t;
    div.setAttribute("p", pathPos[x+"x"+y]!==undefined ? pathPos[x+"x"+y] : "");
    div._xy = [x,y];
    box.appendChild(div);
  }));

  if (!_box)
    return document.body.appendChild(box);

  box._matrix = matrix;
  box._start = start;
  box._end = end;
  box.onmouseup = e =>
  {
    if (!e.target._xy)
      return;

        if (e.button)
    {
      if ((e.button == 2 && !(e.ctrlKey || e.shiftKey)) ||
            (e.button != 2 && (e.ctrlKey || e.shiftKey)))
        end = e.target._xy;
      else
        start = e.target._xy;
    }
    else
      matrix[e.target._xy[1]][e.target._xy[0]] = ~~!matrix[e.target._xy[1]][e.target._xy[0]];

    matrix = matrix.map(r => r.map(t => t ? 1 : 0));

    showMatrix(matrix, start, end, box);
  }
  box.oncontextmenu = e => e.preventDefault();
}

function custom(matrix, start, end)
{
  if (matrix)
  {
    document.getElementById("columns").value = matrix[0].length;
    document.getElementById("rows").value = matrix.length;
  }
  const cols = ~~document.getElementById("columns").value,
        rows = ~~document.getElementById("rows").value,
        box = document.getElementById("custom");

  if (start)
    box._start = start;
  if (end)
    box._end = end;

  matrix = matrix || box._matrix || [[]];

  if (cols > matrix[0].length)
    matrix.forEach((a,i) => matrix[i] = a.concat(Array(cols-a.length).fill(3)));
  else if (cols < matrix[0].length)
    matrix.forEach(a => a.splice(cols, a.length - cols));

  if (rows > matrix.length)
    matrix = matrix.concat([...Array(rows-matrix.length)].map(e => Array(cols).fill(1)));
  else if (rows < matrix.length)
    matrix.splice(rows, matrix.length - rows);

  matrix = matrix.map(r => r.map(t => t ? 1 : 0));
  showMatrix(matrix, box._start, box._end, box);
}

function random()
{
  let matrix,
      cols = ~~document.getElementById("columns").value,
      rows = ~~document.getElementById("rows").value,
      box = document.getElementById("custom"),
      date = new Date();
  do
  {
    matrix = [...Array(rows)].map(e => [...Array(cols)].map( e=> Math.round(Math.random()*1.4))); //generate less dense matrix
    path = shortestPath(matrix, box._start, box._end);
  }
  while(path.length<2 && new Date - date < 10000) //10 sec max

  matrix = matrix.map(r=>r.map(a=>Math.round(Math.random()*a*0.9))); //fake more density
    path.forEach(a=>matrix[a[1]][a[0]]=1); //clear the path
  custom(matrix);
}

.matrix:not(:empty)
{
  display: inline-grid;
  grid-gap: 1px;
  border: 1px solid black;
  margin: 0.5em;
  width: fit-content;
}
.matrix *
{
  width: 2em;
  height: 2em;
  background-color: grey;
  outline: 1px solid black;
}
.matrix .t1
{
  background-color: white;
}
.matrix .t2
{
  background-color: lightgreen;
}

.matrix *:before
{
  content: attr(p);
  position: absolute;
  width: 2em;
  height: 2em;
  line-height: 2em;
  text-align: center;
  font-size: 1em;
}

.matrix .t3
{
  background-color: green;
}
.matrix .t4
{
  background-color: red;
}
.custom .matrix
{
}
.custom .matrix :hover
{
  opacity: 0.8;
  box-shadow: 0 0 5px 1px black;
  z-index: 1;
}
.custom .matrix :hover:after
{
  content: "";
  display: block;
  width: 100%;
  height: 100%;
  box-shadow: 0 0 5px 1px black inset;
}
.custom .matrix .t1:hover
{
  background-color: #CCC;
}
input
{
  width: 3em;
}
.custom
{
  display: inline-grid;
  vertical-align: top;
  padding: 0.5em;
  padding-bottom: 3em;
}

.as-console-wrapper
{
  max-height: 3em !important;
}

<span class="custom">
  <div>
    Width: <input id="columns" type="number" min="3" max="100" oninput="custom()">
    Height: <input id="rows" type="number" min="3" max="100" oninput="custom()">
    <button onclick="random()">random</button>
  </div>
  <div>Middle Click = set start position</div>
  <div>Right Click = set end position</div>
  <div id="custom"></div>
</span>