javascript 矩阵最短路径

bxgwgixi  于 2023-11-15  发布在  Java
关注(0)|答案(1)|浏览(139)

我可以向左、向右、向上、向下移动--不允许有对角线移动。
只能移动到包含1而不是0的单元格。
从左上角单元格开始(0,0)
结束于右下角单元格(2,3)
最后一个单元格未定义,应为(2,3)。

  1. let visited = [[false, false, false, false],
  2. [false, false, false, false],
  3. [false, false, false, false]]
  4. function shortestPath(arr, c, r) {
  5. if (arr.length === c + 1 && arr[0].length === r + 1) {
  6. if (arr[c][r] === 1) {
  7. return true;
  8. }
  9. else { return false }
  10. }
  11. if (c === arr.length || r === arr[0].length || c < 0 || r < 0) { return }
  12. console.log(r, c)
  13. if (arr[c][r] === 0) { return }
  14. if (visited[c][r]) { return }
  15. visited[c][r] = true
  16. shortestPath(arr, c, r + 1)
  17. shortestPath(arr, c + 1, r)
  18. shortestPath(arr, c, r - 1)
  19. shortestPath(arr, c - 1, r)
  20. }
  21. let a = [[1, 1, 1, 0],
  22. [1, 1, 0, 1],
  23. [1, 1, 1, 1]]
  24. console.log(shortestPath(a, 0, 0))

字符串
输出量:
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
未定义

t1qtbnec

t1qtbnec1#

标签:https://jsfiddle.net/vanowm/j0dxqy7h/

  1. function shortestPath(arr, start, end)
  2. {
  3. arr = arr.map(a => [...a]); //clone matrix, so we can re-use it by updating which coordinates we've visited
  4. if (!start)
  5. start = [0, 0];
  6. if (!end)
  7. end = [arr[0].length-1, arr.length-1];
  8. arr[start[1]][start[0]] = 0; //set start position as unavailable
  9. const paths = [[start]];
  10. while (paths.length)
  11. {
  12. 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)
  13. cur = path[path.length-1], //get last coordinates from the path
  14. next = [ //next coordinates from current position
  15. [cur[0], cur[1] + 1],
  16. [cur[0] + 1, cur[1]],
  17. [cur[0], cur[1] - 1],
  18. [cur[0] - 1, cur[1]],
  19. ];
  20. for (let i = 0, pos; i < next.length; i++)
  21. {
  22. pos = next[i];
  23. if (pos[0] == end[0] && pos[1] == end[1])
  24. return path.concat([end]); //found end position
  25. if (pos[0] < 0 || pos[0] >= arr[0].length || //check boundaries for x
  26. pos[1] < 0 || pos[1] >= arr.length || //check boundaries for y
  27. !arr[pos[1]][pos[0]]) //position available?
  28. {
  29. continue;
  30. }
  31. arr[pos[1]][pos[0]] = 0; //mark position unavailable
  32. paths.push(path.concat([pos])); //add position to the path
  33. }
  34. }
  35. return [start]; //return start coordinates if no path found
  36. }
  37. showMatrix([
  38. [1, 1, 1, 0],
  39. [1, 1, 0, 1],
  40. [1, 1, 1, 1]
  41. ]);
  42. custom([
  43. [1,1,0,1,1,1,1,0],
  44. [1,0,1,1,0,0,1,1],
  45. [1,0,1,0,1,1,0,1],
  46. [1,0,1,1,0,1,1,1],
  47. [1,0,0,1,0,1,0,0],
  48. [1,1,0,1,0,1,1,1],
  49. [1,0,1,1,1,0,0,1],
  50. [1,1,0,0,1,0,1,1],
  51. [0,1,1,1,1,0,1,1]
  52. ], [1,0],[6,7]);
  53. function showMatrix(matrix, start, end, _box)
  54. {
  55. if (!start || start[0] >= matrix[0].length || start[1] >= matrix.length)
  56. start = [0, 0];
  57. if (!end || end[0] >= matrix[0].length || end[1] >= matrix.length)
  58. end = [matrix[0].length-1, matrix.length-1];
  59. const path = shortestPath(matrix, start, end);
  60. console.log("matrix:", JSON.stringify(matrix));
  61. console.log("path:", path.join("|"));
  62. path.forEach(b => matrix[b[1]][b[0]] = 2); //merge path into matrix
  63. matrix[start[1]][start[0]] = 3; //identify start
  64. matrix[end[1]][end[0]] = 4; //identify end
  65. let div = document.createElement("div");
  66. const box = _box || div.cloneNode();
  67. box.className = "matrix";
  68. box.innerHTML = "";
  69. box.style.gridTemplateColumns = "1fr ".repeat(matrix[0].length);
  70. const pathPos = {};
  71. path.forEach((a,i) => pathPos[a.join("x")] = i);
  72. matrix.forEach((r, y) => r.forEach((t, x) =>
  73. {
  74. div = div.cloneNode(false);
  75. div.className = "t" + t;
  76. div.setAttribute("p", pathPos[x+"x"+y]!==undefined ? pathPos[x+"x"+y] : "");
  77. div._xy = [x,y];
  78. box.appendChild(div);
  79. }));
  80. if (!_box)
  81. return document.body.appendChild(box);
  82. box._matrix = matrix;
  83. box._start = start;
  84. box._end = end;
  85. box.onmouseup = e =>
  86. {
  87. if (!e.target._xy)
  88. return;
  89. if (e.button)
  90. {
  91. if ((e.button == 2 && !(e.ctrlKey || e.shiftKey)) ||
  92. (e.button != 2 && (e.ctrlKey || e.shiftKey)))
  93. end = e.target._xy;
  94. else
  95. start = e.target._xy;
  96. }
  97. else
  98. matrix[e.target._xy[1]][e.target._xy[0]] = ~~!matrix[e.target._xy[1]][e.target._xy[0]];
  99. matrix = matrix.map(r => r.map(t => t ? 1 : 0));
  100. showMatrix(matrix, start, end, box);
  101. }
  102. box.oncontextmenu = e => e.preventDefault();
  103. }
  104. function custom(matrix, start, end)
  105. {
  106. if (matrix)
  107. {
  108. document.getElementById("columns").value = matrix[0].length;
  109. document.getElementById("rows").value = matrix.length;
  110. }
  111. const cols = ~~document.getElementById("columns").value,
  112. rows = ~~document.getElementById("rows").value,
  113. box = document.getElementById("custom");
  114. if (start)
  115. box._start = start;
  116. if (end)
  117. box._end = end;
  118. matrix = matrix || box._matrix || [[]];
  119. if (cols > matrix[0].length)
  120. matrix.forEach((a,i) => matrix[i] = a.concat(Array(cols-a.length).fill(3)));
  121. else if (cols < matrix[0].length)
  122. matrix.forEach(a => a.splice(cols, a.length - cols));
  123. if (rows > matrix.length)
  124. matrix = matrix.concat([...Array(rows-matrix.length)].map(e => Array(cols).fill(1)));
  125. else if (rows < matrix.length)
  126. matrix.splice(rows, matrix.length - rows);
  127. matrix = matrix.map(r => r.map(t => t ? 1 : 0));
  128. showMatrix(matrix, box._start, box._end, box);
  129. }
  130. function random()
  131. {
  132. let matrix,
  133. cols = ~~document.getElementById("columns").value,
  134. rows = ~~document.getElementById("rows").value,
  135. box = document.getElementById("custom"),
  136. date = new Date();
  137. do
  138. {
  139. matrix = [...Array(rows)].map(e => [...Array(cols)].map( e=> Math.round(Math.random()*1.4))); //generate less dense matrix
  140. path = shortestPath(matrix, box._start, box._end);
  141. }
  142. while(path.length<2 && new Date - date < 10000) //10 sec max
  143. matrix = matrix.map(r=>r.map(a=>Math.round(Math.random()*a*0.9))); //fake more density
  144. path.forEach(a=>matrix[a[1]][a[0]]=1); //clear the path
  145. custom(matrix);
  146. }
  1. .matrix:not(:empty)
  2. {
  3. display: inline-grid;
  4. grid-gap: 1px;
  5. border: 1px solid black;
  6. margin: 0.5em;
  7. width: fit-content;
  8. }
  9. .matrix *
  10. {
  11. width: 2em;
  12. height: 2em;
  13. background-color: grey;
  14. outline: 1px solid black;
  15. }
  16. .matrix .t1
  17. {
  18. background-color: white;
  19. }
  20. .matrix .t2
  21. {
  22. background-color: lightgreen;
  23. }
  24. .matrix *:before
  25. {
  26. content: attr(p);
  27. position: absolute;
  28. width: 2em;
  29. height: 2em;
  30. line-height: 2em;
  31. text-align: center;
  32. font-size: 1em;
  33. }
  34. .matrix .t3
  35. {
  36. background-color: green;
  37. }
  38. .matrix .t4
  39. {
  40. background-color: red;
  41. }
  42. .custom .matrix
  43. {
  44. }
  45. .custom .matrix :hover
  46. {
  47. opacity: 0.8;
  48. box-shadow: 0 0 5px 1px black;
  49. z-index: 1;
  50. }
  51. .custom .matrix :hover:after
  52. {
  53. content: "";
  54. display: block;
  55. width: 100%;
  56. height: 100%;
  57. box-shadow: 0 0 5px 1px black inset;
  58. }
  59. .custom .matrix .t1:hover
  60. {
  61. background-color: #CCC;
  62. }
  63. input
  64. {
  65. width: 3em;
  66. }
  67. .custom
  68. {
  69. display: inline-grid;
  70. vertical-align: top;
  71. padding: 0.5em;
  72. padding-bottom: 3em;
  73. }
  74. .as-console-wrapper
  75. {
  76. max-height: 3em !important;
  77. }
  1. <span class="custom">
  2. <div>
  3. Width: <input id="columns" type="number" min="3" max="100" oninput="custom()">
  4. Height: <input id="rows" type="number" min="3" max="100" oninput="custom()">
  5. <button onclick="random()">random</button>
  6. </div>
  7. <div>Middle Click = set start position</div>
  8. <div>Right Click = set end position</div>
  9. <div id="custom"></div>
  10. </span>
展开查看全部

相关问题