javascriptmatrixmultidimensional-array

Matrix Shortest Path


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


Solution

  • 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>