This is comment for paste
Hole
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Here's an implementation of the algorithm using JavaScript and HTML:
- <!DOCTYPE html>
- <html lang="en">
- <head>
- <meta charset="UTF-8">
- <meta name="viewport" content="width=device-width, initial-scale=1.0">
- <title>Grid Algorithm</title>
- </head>
- <body>
- <script>
- class A {
- constructor(i, j, w) {
- this.i = i;
- this.j = j;
- this.w = w;
- }
- static compare(a, b) {
- return a.w - b.w;
- }
- }
- function main(n, x, y, obstacles) {
- const cost = Array.from({ length: 1002 }, () => Array(1002).fill(0));
- const dis = Array.from({ length: 1002 }, () => Array(1002).fill(1e9));
- const dir = [[1, -1, 0, 0], [0, 0, 1, -1]];
- obstacles.forEach(([u, v]) => cost[v][u] = 1);
- dis[x][y] = 0;
- const heap = [new A(x, y, 0)];
- while (heap.length > 0) {
- heap.sort(A.compare);
- const now = heap.shift();
- if (now.i > 1000 || now.i < 1 || now.j > 1000 || now.j < 1) {
- return dis[now.i][now.j];
- }
- for (let k = 0; k < 4; k++) {
- const ni = now.i + dir[0][k];
- const nj = now.j + dir[1][k];
- if (ni > 1001 || ni < 0 || nj > 1001 || nj < 0) continue;
- if (dis[ni][nj] != 1e9) continue;
- dis[ni][nj] = dis[now.i][now.j] + cost[ni][nj];
- heap.push(new A(ni, nj, dis[ni][nj]));
- }
- }
- return 0;
- }
- // Example usage
- const n = 4;
- const x = 5;
- const y = 5;
- const obstacles = [
- [3, 4],
- [3, 5],
- [3, 6],
- [5, 3]
- ];
- const result = main(n, x, y, obstacles);
- console.log(result);
- </script>
- </body>
- </html>
- This code uses HTML to create a basic webpage structure and JavaScript to implement the algorithm. The main function takes 4 parameters: the number of obstacles n, the starting position x and y, and an array of obstacles (each an array with two elements, [u, v]). The main function will return the shortest path from the starting point (x, y) to any boundary cell of the grid while considering the cost of traversing specific cells. You can adjust the input values in the example usage to test the algorithm.
Advertisement
Add Comment
Please, Sign In to add comment