fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //===============typedef
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7. typedef vector< vi > vvi;
  8. typedef pair<int, int> ii;
  9. typedef vector<ii> vii;
  10. typedef vector<vii> vvii;
  11. typedef set<int> si;
  12. typedef map<string, int> msi;
  13. //=================
  14. const  ll mod=1e9+7;
  15.  
  16.  
  17. //=============define
  18. #define inf 10000000
  19. #define cln(a) memset(a,0,sizeof a);
  20. #define clni(a) memset(a,inf,sizeof a);
  21. #define all(x) x.begin(), x.end()
  22. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  23. #define sz(a) int((a).size())
  24. #define pb push_back
  25. #define sp(c,x) ((c).find(x) != (c).end())  // for set,map
  26. #define vp(c,x) (find(all(c),x) != (c).end())  // for vector
  27. #define uu first
  28. #define vv second
  29. #define fr(i,a,b) for(int i=int(a);i<int(b);++i)
  30. #define nfr(i,a,b) for(int i= int(a);i>=int(b);--i)
  31. #define tc cin>>t ; while(t--)
  32. #define pc()  cout<<"Case "<<cs++<<": "
  33. #define mx (int)1e5+10
  34. #define sc2(x,y) int x,y;scanf("%d %d",&x,&y)
  35. #define sc3(x,y,z) int x,y,z;scanf("%d %d %d",&x,&y,&z)
  36. #define sc(x) int x; scanf("%d",&x)
  37. #define pfs(x) printf("%d ",x)
  38. #define pf(x) printf("%d\n",x)
  39. #define el puts("");
  40. #define getcx() getchar()
  41. #define Fi freopen("inp.txt","r",stdin)
  42. #define rt return 0
  43. #define dbg(x) cerr<<x<<endl
  44. //============functions
  45. ll bigmod(ll a,ll b)
  46. {
  47.     ll ans=1;
  48.     while(b)
  49.     {
  50.     if(b&1)
  51.     ans=(ans*a)%mod;
  52.     a=(a*a)%mod;
  53.     b>>=1;
  54.     }
  55.     return ans;
  56. }
  57.  
  58. int dx[]={0,0,1,-1};
  59. int dy[]={1,-1,0,0}; 
  60. //int vis[505][505];
  61. //int vis[505]
  62. //string s[505];
  63. void dfs(int u,int v)
  64. {
  65.  
  66. }
  67. int n,m;
  68. char g[505][505];
  69. int dis[505][505];
  70. int Int(char c)
  71. {
  72.     return isdigit(c)?c-48:0;
  73. }
  74. void floyd()
  75. { 
  76.   for(int k=0;k<n;k++)
  77.     for(int i=0;i<n;i++)
  78.     for(int j=0;j<n;j++)
  79.  
  80.             if(g[i][k]+g[k][j]<g[i][j])
  81.                 g[i][j]=g[i][k]+g[k][j];
  82. }
  83. ii s,t;
  84. int spfa()
  85. {       
  86.     fr(i,0,n)
  87.     fr(j,0,m) 
  88.         dis[i][j]=inf;
  89.     dis[s.uu][s.vv]=0;
  90.     queue< ii > q;
  91.     q.push(s);
  92.     while(!q.empty())
  93.     {
  94.         ii tm=q.front();
  95.         q.pop();
  96.         if(tm.uu==t.uu && tm.vv==t.vv)
  97.             return dis[t.uu][t.vv];
  98.  
  99.         fr(i,0,4)
  100.         {
  101.             ii nw;
  102.             nw.uu=tm.uu+dx[i];
  103.             nw.vv=tm.vv+dy[i];
  104.             if(g[nw.uu][nw.vv]!='#' && dis[nw.uu][nw.vv]>dis[tm.uu][tm.vv]+Int(g[nw.uu][nw.vv]))
  105.             {
  106.              dis[nw.uu][nw.vv]=dis[tm.uu][tm.vv]+Int(g[nw.uu][nw.vv]);
  107.              q.push({nw});   
  108.             }           
  109.         }
  110.     } 
  111.     return dis[t.uu][t.vv];
  112. }
  113.  
  114. int main()
  115. {
  116.     cin>>n>>m;
  117.     fr(i,0,n)
  118.     {
  119.         fr(j,0,m)
  120.         {
  121.             cin>>g[i][j];
  122.             if(g[i][j]=='H')
  123.                 s={i,j};
  124.             else if(g[i][j]=='E')
  125.                 t={i,j};
  126.         }
  127.     }
  128.     int ans=spfa();
  129.     if(ans==inf)
  130.         puts("ARTSKJID");
  131.     else cout<<ans<<endl;
  132. }
Success #stdin #stdout 0s 17312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9xc2mJ
language:
C++ (gcc 8.3)
created:
8 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!