Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Jul 6th, 2013  |  syntax: None  |  size: 3.12 KB  |  hits: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5. struct koord
  6. {
  7.        int x;
  8.        int y;
  9.        koord(int _x=0,int _y=0)
  10.        {
  11.                  x=_x;
  12.                  y=_y;
  13.        }
  14. };
  15. queue<koord>Q;
  16. bool bio[150][150];
  17. int dx[]={0,0,1,-1};
  18. int dy[]={1,-1,0,0};
  19. int dist[150][150];
  20. char polje[150][150];
  21. int a,b;
  22. void bfs(int a1,int b1)
  23. {
  24.      Q.push(koord(a1,b1));
  25.      bio[a1][b1]=true;
  26.      while(!Q.empty())
  27.      {
  28.                       koord pos=Q.front();
  29.                       Q.pop();
  30.                       for(int i=0;i<4;++i)
  31.                       {
  32.                               koord dalje=koord(pos.x+dx[i],pos.y+dy[i]);
  33.                               if(dalje.x>=0 && dalje.x<b && dalje.y>=0 && dalje.y<a)
  34.                               {
  35.                                 if(polje[dalje.x][dalje.y]!='X' || polje[dalje.x][dalje.y]!='S')
  36.                                 if(bio[dalje.x][dalje.y]==false)
  37.                                 {
  38.                                     if(polje[dalje.x][dalje.y]=='D')
  39.                                     {
  40.                                          bio[dalje.x][dalje.y]=true;
  41.                                          dist[dalje.x][dalje.y]=dist[pos.x][pos.y];
  42.                                          Q.push(dalje);
  43.                                     }
  44.                                     else
  45.                                     {
  46.                                     bio[dalje.x][dalje.y]=true;
  47.                                     dist[dalje.x][dalje.y]=dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0');
  48.                                     Q.push(dalje);
  49.                                     }
  50.                                 }
  51.                                 if(polje[dalje.x][dalje.y]=='D' && dist[dalje.x][dalje.y]>dist[pos.x][pos.y])
  52.                                 {
  53.                                     dist[dalje.x][dalje.y]=dist[pos.x][pos.y];
  54.                                     Q.push(dalje);                      
  55.                                 }
  56.                                 else if(dist[dalje.x][dalje.y]>dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0'))
  57.                                 {
  58.                                     dist[dalje.x][dalje.y]=dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0');
  59.                                     Q.push(dalje);
  60.                                 }
  61.                               }
  62.                       }
  63.      }
  64. }
  65. int main()
  66. {
  67.     scanf("%d%d",&a,&b);
  68.     while(a!=0 && b!=0)
  69.     {
  70.                int c=0,d=0,e=0,f=0;
  71.                for(int i=0;i<b;++i)scanf("%s",polje[i]);
  72.                //scanf("\n");
  73.                for(int i=0;i<b;++i)
  74.                for(int j=0;j<a;++j)
  75.                {
  76.                        if(polje[i][j]=='S'){c=i;d=j;}
  77.                        if(polje[i][j]=='D'){e=i;f=j;}
  78.                }
  79.                bfs(c,d);
  80.                printf("%d\n",dist[e][f]);
  81.                for(int i=0;i<150;++i)
  82.                for(int j=0;j<150;++j){bio[i][j]=false;dist[i][j]=0;}
  83.                Q.empty();
  84.                scanf("%d%d",&a,&b);
  85.     }
  86.     return 0;
  87. }