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