fork(2) download
copy 
  1. /*
  2. Written by: Yash Kumar (yashkumar18)
  3. Dhirubhai Ambani Institute Of Information And Communication Technology, Gandhinagar (DA-IICT GANDHINAGAR)
  4. 1st Year ICT BTECH student
  5. */
  6.  
  7. #include<stdio.h>
  8. #include<iostream>
  9. #include<iomanip>
  10. #include<algorithm>
  11. #include<math.h>
  12. #include<cstdio>
  13. #include<ctype.h>
  14. #include<cstring>
  15. #include<string.h>
  16. #include<inttypes.h>
  17. #include<vector>
  18. #include<set>
  19. #include<map>
  20. #include<queue>
  21. #include<stack>
  22. #include<functional>
  23. #include<cmath>
  24. #include<cstdlib>
  25. #include<cassert>
  26.  
  27. #define lli long long int
  28. #define llu unsigned long long int
  29.  
  30. #define sllu(a) scanf("%llu",&a)
  31. #define sllu2(a,b) scanf("%llu %llu",&a,&b)
  32. #define sllu3(a,b,c) scanf("%llu %llu %llu",&a,&b,&c)
  33. #define sllu4(a,b,c,d) scanf("%llu %llu %llu %llu",&a,&b,&c,&d)
  34. #define sllu5(a,b,c,d,e) scanf("%llu %llu %llu %llu %llu",&a,&b,&c,&d,&e)
  35. #define si(a) scanf("%d",&a)
  36. #define si2(a,b) scanf("%d %d",&a,&b)
  37. #define si3(a,b,c) scanf("%d %d %d",&a,&b,&c)
  38. #define si4(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
  39. #define si5(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
  40. #define slli(a) scanf("%lld",&a)
  41. #define slli2(a,b) scanf("%lld %lld",&a,&b)
  42. #define slli3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
  43. #define slli4(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
  44. #define slli5(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
  45. #define ss(a) scanf("%s",a)
  46. #define sc(a) scanf("%c",&a)
  47. #define sf(a) scanf("%f",&a)
  48. #define sf2(a,b) scanf("%f %f",&a,&b)
  49. #define sf3(a,b,c) scanf("%f %f %f",&a,&b,&c)
  50. #define sf4(a,b,c,d) scanf("%f %f %f %f",&a,&b,&c,&d)
  51. #define sf5(a,b,c,d,e) scanf("%f %f %f %f %f",&a,&b,&c,&d,&e)
  52. #define sd(a) scanf("%lf",&a)
  53. #define sd2(a,b) scanf("%lf %lf",&a,&b)
  54. #define sd3(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
  55. #define sd4(a,b,c,d) scanf("%lf %lf %lf %lf",&a,&b,&c,&d)
  56. #define sd5(a,b,c,d,e) scanf("%lf %lf %lf %lf %lf",&a,&b,&c,&d,&e)
  57. #define slluarray(a,n) for(lli i=0;i<n;i++)sllu(a[i])
  58. #define siarray(a,n) for(lli i=0;i<n;i++)si(a[i])
  59. #define slliarray(a,n) for(lli i=0;i<n;i++)slli(a[i])
  60. #define sfarray(a,n) for(lli i=0;i<n;i++)sf(a[i])
  61. #define sdarray(a,n) for(lli i=0;i<n;i++)sd(a[i])
  62.  
  63. #define plli(a) printf("%lld",a)
  64. #define pllin(a) printf("%lld\n",a)
  65. #define pi(a) printf("%d",a)
  66. #define pin(a) printf("%d\n",a)
  67. #define pllu(a) printf("%llu",a)
  68. #define pllun(a) printf("%llu\n",a)
  69. #define ps(a) printf("%s",a)
  70. #define psn(a) printf("%s\n",a)
  71. #define pc(a) printf("%c",a)
  72. #define pcn(a) printf("c\n",a)
  73. #define pn() printf("\n")
  74. #define pspace() printf(" ")
  75. #define pf(a) printf("%f",a)
  76. #define pfn(a) printf("f\n",a)
  77. #define pd(a) printf("%lf",a)
  78. #define pdn(a) printf("lf\n",a)
  79. #define plliarray(a,n) for(lli i=0;i<n;i++)printf("%lld ",a[i])
  80. #define piarray(a,n) for(lli i=0;i<n;i++)printf("%d ",a[i])
  81. #define plluarray(a,n) for(lli i=0;i<n;i++)printf("%llu ",a[i])
  82. #define pfarray(a,n) for(lli i=0;i<n;i++)printf("%f ",a[i])
  83. #define pdarray(a,n) for(lli i=0;i<n;i++)printf("%lf ",a[i])
  84.  
  85. #define max(a,b)(a>b?a:b)
  86. #define min(a,b)(a<b?a:b)
  87. #define abs(a) (a>0?a:-a)
  88.  
  89. #define MOD 1000000007
  90.  
  91. using namespace std;
  92. #define MAXN 25
  93. #define MAXNN 625
  94.  
  95. char s[MAXN][MAXN];
  96. int cur,start,dest,n,m;
  97. vector<int> edge[MAXNN],cost[MAXNN];
  98. int dist[MAXNN];
  99. deque<int> Q;
  100. int u,v,t,pos;
  101.  
  102. int main()
  103. {
  104.     si2(m,n);
  105.  
  106.     for(int i=0;i<n;i++)
  107.         ss(s[i]);
  108.  
  109.     for(int i=0;i<n;i++)
  110.     {
  111.         for(int j=0;j<m;j++)
  112.         {
  113.             cur=i*m+j;
  114.             if(s[i][j]=='X')
  115.                 continue;
  116.             if(s[i][j]=='S')
  117.                 start=cur;
  118.             if(s[i][j]=='D')
  119.                 dest=cur;
  120.  
  121.             if(i>0)
  122.             {
  123.                 if(s[i-1][j]!='X')
  124.                 {
  125.                     edge[cur].push_back( (i-1)*m + (j) );
  126.                     if(s[i-1][j]=='S' || s[i-1][j]=='D')
  127.                         cost[cur].push_back(0);
  128.                     else
  129.                         cost[cur].push_back(s[i-1][j]-'0');
  130.                 }
  131.             }
  132.             if(i<n-1)
  133.             {
  134.                 if(s[i+1][j]!='X')
  135.                 {
  136.                     edge[cur].push_back( (i+1)*m + (j) );
  137.                     if(s[i+1][j]=='S' || s[i+1][j]=='D')
  138.                         cost[cur].push_back(0);
  139.                     else
  140.                         cost[cur].push_back(s[i+1][j]-'0');
  141.                 }
  142.             }
  143.  
  144.             if(j>0)
  145.             {
  146.                 if(s[i][j-1]!='X')
  147.                 {
  148.                     edge[cur].push_back( (i)*m + (j-1) );
  149.                     if(s[i][j-1]=='S' || s[i][j-1]=='D')
  150.                         cost[cur].push_back(0);
  151.                     else
  152.                         cost[cur].push_back(s[i][j-1]-'0');
  153.                 }
  154.             }
  155.             if(j<m-1)
  156.             {
  157.                 if(s[i][j+1]!='X')
  158.                 {
  159.                     edge[cur].push_back( (i)*m + (j+1) );
  160.                     if(s[i][j+1]=='S' || s[i][j+1]=='D')
  161.                         cost[cur].push_back(0);
  162.                     else
  163.                         cost[cur].push_back(s[i][j+1]-'0');
  164.                 }
  165.             }
  166.         }
  167.     }
  168.  
  169.     for(int i=0;i<n*m;i++)
  170.     {
  171.         dist[i]=10000000;
  172.         Q.push_back(i);
  173.     }
  174.     dist[start]=0;
  175.  
  176.  
  177.     while(!Q.empty())
  178.     {
  179.         cur=100000000;
  180.         for(int i=0;i<Q.size();i++)
  181.         {
  182.             t=Q[i];
  183.             if(dist[t]<cur)
  184.             {
  185.                 cur=dist[t];
  186.                 u=t;
  187.                 pos=i;
  188.             }
  189.         }
  190.         Q.erase(Q.begin()+pos);
  191.  
  192.         for(int i=0;i<edge[u].size();i++)
  193.         {
  194.             v=edge[u][i];
  195.             if(dist[v]>dist[u]+cost[u][i])
  196.                 dist[v]=dist[u]+cost[u][i];
  197.         }
  198.     }
  199.  
  200.     pi(dist[dest]);
  201.  
  202.     return 0;
  203. }
  204.  
Success #stdin #stdout 0s 2840KB
comments (?)
stdin
copy 
5 5
S5213
2X2X5
51248
4X4X2
1445D
stdout
copy 
23
https://ideone.com/DRYEzE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!