Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream f("ubuph.in");
  4. ofstream g("ubuph.out");
  5. int n,m,v[1005][1005],c[1005][1005];
  6. long long b[1005][1005];
  7. queue < pair <int,int> >a;
  8. bool ok(int i,int j)
  9. {
  10. if(i<1 or j<1 or i>n or j>m)
  11. return 0;
  12. if(c[i][j]==-1)
  13. return 0;
  14. return 1;
  15. }
  16. void lee(int x, int y)
  17. {
  18. int i,j,k,l9,c9;
  19. int dx[]= {1,0,-1,0};
  20. int dy[]= {0,1,0,-1};
  21. c[x][y]=-1;
  22. a.push(make_pair(x,y));
  23. while(!a.empty())
  24. {
  25. i=a.front().first;
  26. j=a.front().second;
  27. c[i][j]=-1;
  28. a.pop();
  29. for(k=0; k<=3; k++)
  30. {
  31. l9=i+dx[k];
  32. c9=j+dy[k];
  33. if(ok(l9,c9)==1)
  34. {
  35. if(b[l9][c9]==-1)
  36. b[l9][c9]=v[i][j]+v[l9][c9];
  37. else if(b[i][j]+v[l9][c9]<b[l9][c9])
  38. b[l9][c9]=b[i][j]+v[l9][c9];
  39. a.push(make_pair(l9,c9));
  40. }
  41. }
  42. }
  43. }
  44. int main()
  45. {
  46. int i,j,xstart,ystart,xfinal,yfinal;
  47. f>>n>>m;
  48. for(i=1; i<=n; i++)
  49. for(j=1; j<=m; j++)
  50. {
  51. f>>v[i][j];
  52. b[i][j]=-1;
  53. }
  54. f>>xstart>>ystart>>xfinal>>yfinal;
  55. b[xstart][ystart]=v[xstart][ystart];
  56. lee(xstart,ystart);
  57. g<<b[xfinal][yfinal];
  58. g<<'\n';
  59. for(i=1; i<=n; i++)
  60. {
  61. for(j=1; j<=m; j++)
  62. g<<b[i][j]<<' ';
  63. g<<'\n';
  64. }
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement