MAGCARI

Hole

May 3rd, 2023
701
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. /*
  2.     Task    : Ball (DFS)
  3.     Author  : Phumipat C. [MAGCARI]
  4.     Language: C++
  5.     Created : 03 May 2023 [18:53]
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. struct A{
  10.     int i,j,w;
  11.     bool operator < (const A&o) const{
  12.         return w > o.w;
  13.     }
  14. };
  15. priority_queue<A > heap;
  16. int cost[1010][1010];
  17. int dis[1010][1010];
  18. int dir[2][4] = {{1,-1,0,0},{0,0,1,-1}};
  19. int main(){
  20.     int n,y,x;
  21.     scanf("%d %d %d",&n,&y,&x);
  22.     for(int i=1;i<=n;i++){
  23.         int u,v;
  24.         scanf("%d %d",&u,&v);
  25.         cost[v][u] = 1;
  26.     }
  27.     for(int i=0;i<=1001;i++)
  28.         for(int j=0;j<=1001;j++)
  29.             dis[i][j] = 1e9;
  30.     heap.push({x,y,0});
  31.     dis[x][y] = 0;
  32.     while(!heap.empty()){
  33.         A now = heap.top();
  34.         heap.pop();
  35.         // stop
  36.         if(now.i > 1000 || now.i < 1 || now.j > 1000 || now.j < 1){
  37.             printf("%d\n",dis[now.i][now.j]);
  38.             return 0;
  39.         }
  40.         // process
  41.         for(int k=0;k<4;k++){
  42.             int ni = now.i + dir[0][k];
  43.             int nj = now.j + dir[1][k];
  44.             if(ni > 1001 || ni < 0 || nj > 1001 || nj < 0)  continue;
  45.             if(dis[ni][nj] != 1e9)                          continue;
  46.             dis[ni][nj] = dis[now.i][now.j] + cost[ni][nj];
  47.             heap.push({ni,nj,dis[ni][nj]});
  48.         }
  49.     }
  50.     return 0;
  51. }
Advertisement
Comments
  • a_nun
    2 years
    # text 2.19 KB | 0 0
    1. Here's an implementation of the algorithm using JavaScript and HTML:
    2.  
    3. <!DOCTYPE html>
    4. <html lang="en">
    5. <head>
    6. <meta charset="UTF-8">
    7. <meta name="viewport" content="width=device-width, initial-scale=1.0">
    8. <title>Grid Algorithm</title>
    9. </head>
    10. <body>
    11. <script>
    12. class A {
    13. constructor(i, j, w) {
    14. this.i = i;
    15. this.j = j;
    16. this.w = w;
    17. }
    18.  
    19. static compare(a, b) {
    20. return a.w - b.w;
    21. }
    22. }
    23.  
    24. function main(n, x, y, obstacles) {
    25. const cost = Array.from({ length: 1002 }, () => Array(1002).fill(0));
    26. const dis = Array.from({ length: 1002 }, () => Array(1002).fill(1e9));
    27. const dir = [[1, -1, 0, 0], [0, 0, 1, -1]];
    28.  
    29. obstacles.forEach(([u, v]) => cost[v][u] = 1);
    30. dis[x][y] = 0;
    31.  
    32. const heap = [new A(x, y, 0)];
    33.  
    34. while (heap.length > 0) {
    35. heap.sort(A.compare);
    36. const now = heap.shift();
    37.  
    38. if (now.i > 1000 || now.i < 1 || now.j > 1000 || now.j < 1) {
    39. return dis[now.i][now.j];
    40. }
    41.  
    42. for (let k = 0; k < 4; k++) {
    43. const ni = now.i + dir[0][k];
    44. const nj = now.j + dir[1][k];
    45.  
    46. if (ni > 1001 || ni < 0 || nj > 1001 || nj < 0) continue;
    47. if (dis[ni][nj] != 1e9) continue;
    48.  
    49. dis[ni][nj] = dis[now.i][now.j] + cost[ni][nj];
    50. heap.push(new A(ni, nj, dis[ni][nj]));
    51. }
    52. }
    53.  
    54. return 0;
    55. }
    56.  
    57. // Example usage
    58. const n = 4;
    59. const x = 5;
    60. const y = 5;
    61. const obstacles = [
    62. [3, 4],
    63. [3, 5],
    64. [3, 6],
    65. [5, 3]
    66. ];
    67. const result = main(n, x, y, obstacles);
    68. console.log(result);
    69.  
    70. </script>
    71. </body>
    72. </html>
    73. 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.
Add Comment
Please, Sign In to add comment