Advertisement
Guest User

Untitled

a guest
Jul 6th, 2013
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.12 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement