Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <queue>
- #include <algorithm>
- using namespace std;
- struct koord
- {
- int x;
- int y;
- koord(int _x=0,int _y=0)
- {
- x=_x;
- y=_y;
- }
- };
- queue<koord>Q;
- bool bio[150][150];
- int dx[]={0,0,1,-1};
- int dy[]={1,-1,0,0};
- int dist[150][150];
- char polje[150][150];
- int a,b;
- void bfs(int a1,int b1)
- {
- Q.push(koord(a1,b1));
- bio[a1][b1]=true;
- while(!Q.empty())
- {
- koord pos=Q.front();
- Q.pop();
- for(int i=0;i<4;++i)
- {
- koord dalje=koord(pos.x+dx[i],pos.y+dy[i]);
- if(dalje.x>=0 && dalje.x<b && dalje.y>=0 && dalje.y<a)
- {
- if(polje[dalje.x][dalje.y]!='X' || polje[dalje.x][dalje.y]!='S')
- if(bio[dalje.x][dalje.y]==false)
- {
- if(polje[dalje.x][dalje.y]=='D')
- {
- bio[dalje.x][dalje.y]=true;
- dist[dalje.x][dalje.y]=dist[pos.x][pos.y];
- Q.push(dalje);
- }
- else
- {
- bio[dalje.x][dalje.y]=true;
- dist[dalje.x][dalje.y]=dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0');
- Q.push(dalje);
- }
- }
- if(polje[dalje.x][dalje.y]=='D' && dist[dalje.x][dalje.y]>dist[pos.x][pos.y])
- {
- dist[dalje.x][dalje.y]=dist[pos.x][pos.y];
- Q.push(dalje);
- }
- else if(dist[dalje.x][dalje.y]>dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0'))
- {
- dist[dalje.x][dalje.y]=dist[pos.x][pos.y]+(polje[dalje.x][dalje.y]-'0');
- Q.push(dalje);
- }
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d",&a,&b);
- while(a!=0 && b!=0)
- {
- int c=0,d=0,e=0,f=0;
- for(int i=0;i<b;++i)scanf("%s",polje[i]);
- //scanf("\n");
- for(int i=0;i<b;++i)
- for(int j=0;j<a;++j)
- {
- if(polje[i][j]=='S'){c=i;d=j;}
- if(polje[i][j]=='D'){e=i;f=j;}
- }
- bfs(c,d);
- printf("%d\n",dist[e][f]);
- for(int i=0;i<150;++i)
- for(int j=0;j<150;++j){bio[i][j]=false;dist[i][j]=0;}
- Q.empty();
- scanf("%d%d",&a,&b);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement