fork download 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<vector>
  5. #include<stack>
  6. #include<queue>
  7. #include<set>
  8. #include<algorithm>
  9. #include<functional>
  10. #include<cstring>
  11. #include<deque>
  12. using namespace std;
  13.  
  14. char map[1001][1001];
  15. int dis[1001][1001];
  16. int dx[]={1,-1,0,0};
  17. int dy[]={0,0,1,-1};
  18. struct pos{
  19.     int x,y,w;
  20.     pos(){};
  21.     pos(int _x,int _y,int _w){x=_x;y=_y;w=_w;}
  22. };
  23. int main()
  24. {
  25.     int H,W;
  26.     while(~scanf("%d%d",&H,&W))
  27.     {
  28.         gets(map[0]);
  29.         for(int i=0;i<H;++i)
  30.             gets(map[i]);
  31.         int x,y;
  32.         for(int i=0;i<H;++i)
  33.             for(int j=0;j<W;++j)
  34.                 if(map[i][j]=='E'){
  35.                     x=i;y=j;
  36.                 }
  37.         queue<pos> qu;
  38.         qu.push(pos(x,y,0));
  39.         memset(dis,0x3f,sizeof(dis));
  40.         dis[x][y]=0;
  41.         while(!qu.empty())
  42.         {
  43.             pos t=qu.front();qu.pop();
  44.             for(int i=0;i<4;++i){
  45.                 int nx=t.x+dx[i];
  46.                 int ny=t.y+dy[i];
  47.                 int nw=t.w+1;
  48.                 if(nx<0||H<=nx||ny<0||W<=ny)continue;
  49.                 if(map[nx][ny]=='T')continue;
  50.                 if(dis[nx][ny]==0x3f3f3f3f){
  51.                     dis[nx][ny]=nw;
  52.                     qu.push(pos(nx,ny,nw));
  53.                 }
  54.             }
  55.         }
  56.         /*puts("D");
  57.         for(int p=0;p<H;++p){
  58.             for(int j=0;j<W;++j)
  59.                 cout<<dis[p][j]<<' ';
  60.             cout<<endl;
  61.         }
  62.         cout<<endl;*/
  63.         for(int i=0;i<H;++i)
  64.             for(int j=0;j<W;++j)
  65.                 if(map[i][j]=='S'){
  66.                     x=i;y=j;
  67.                 }
  68.         int lim=dis[x][y],ans=0;
  69.         for(int i=0;i<H;++i)
  70.             for(int j=0;j<W;++j)
  71.                 if('1'<=map[i][j]&&map[i][j]<='9')
  72.                     if(dis[i][j]<=lim)
  73.                         ans+=map[i][j]-'0';
  74.         printf("%d\n",ans);
  75.     }
  76.     return 0;
  77. }
Success #stdin #stdout 0s 8376KB
comments (?)
stdin 
5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
stdout 
3
https://ideone.com/Kq9Fkm
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!