Advertisement
Guest User

Ubuph 100p

a guest
Feb 23rd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <fstream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int s,n,m,a[1001][1001],b[1001][1001];
  6. queue <pair<int,int> > q;
  7. int dx[4]={-1,0,1,0};
  8. int dy[4]={0,1,0,-1};
  9.  
  10. bool interior(int x,int y)
  11. {
  12.     if(x>0 && x<=n && y>0 && y<=m)
  13.         return 1;
  14.     return 0;
  15.  
  16. }
  17. int main()
  18.  
  19. {
  20.     int x,y,x1,y1,i,j,startx,starty,stopx,stopy;
  21.     ifstream f("ubuph.in");
  22.     ofstream g("ubuph.out");
  23.     f>>n>>m;
  24.     for(i=1;i<=n;i++)
  25.         for(j=1;j<=m;j++)
  26.         {
  27.             f>>a[i][j];
  28.             b[i][j]=5001000;
  29.         }
  30.     f>>startx>>starty>>stopx>>stopy;
  31.     q.push(make_pair(startx,starty));
  32.     b[startx][starty]=a[startx][starty];
  33.     while(!q.empty())
  34.     {
  35.         x=q.front().first;
  36.         y=q.front().second;
  37.         for(i=0;i<4;i++)
  38.         {
  39.             x1=x+dx[i];
  40.             y1=y+dy[i];
  41.             if(interior(x1,y1) && b[x][y]+a[x1][y1]<b[x1][y1])
  42.             {
  43.                 b[x1][y1]=b[x][y]+a[x1][y1];
  44.                 q.push(make_pair(x1,y1));
  45.             }
  46.         }
  47.         q.pop();
  48.     }
  49.     g<<b[stopx][stopy];
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement