fork download
copy 
  1. #include <iostream>
  2. #include <deque>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <map>
  6.  
  7. using namespace std;
  8. string mapp="0123456789";
  9. int main()
  10. {
  11.     for (;1!=0;){
  12.    int c,r;
  13.    cin >> c >> r;
  14.    struct point{
  15.    int x,y;
  16.    }start,destination;
  17.    if (c==0&&r==0)break;
  18.    map< int,deque<char> >graph;
  19.    for (int c1(0);c1<r;c1++){
  20.  
  21. string ab;
  22. cin >> ab;
  23. for (int c2(0);c2<c;c2++){
  24. 	char a;
  25. 	a=ab[c2];
  26.  
  27. graph[c1].push_back(a);
  28. if (a=='S'){start.x=c2;start.y=c1;}
  29. if (a=='D'){destination.x=c2;destination.y=c1;}
  30. }
  31. }
  32.  
  33.      int arr[150][150];
  34.      bool check[150][150];
  35.      for (int o(0);o<150;o++)for (int jh(0);jh<150;jh++){arr[o][jh]=56266666;check[o][jh]=false;}
  36.  
  37.      deque<int>ycord;
  38.      deque<int>xcord;
  39.      ycord.push_back(start.y);
  40.      xcord.push_back(start.x);
  41.      arr[start.y][start.x]=0;
  42.      check[start.y][start.x]=true;
  43.      for (;!ycord.empty();){
  44.         if (xcord[0]!=c-1&&graph[ycord[0]][xcord[0]+1]!='X'){
  45.                 if (graph[ycord[0]][xcord[0]+1]=='D'&&arr[ycord[0]][xcord[0]+1]>arr[ycord[0]][xcord[0]])arr[ycord[0]][xcord[0]+1]=arr[ycord[0]][xcord[0]];
  46.  
  47.         else if (graph[ycord[0]][xcord[0]+1]!='D') {
  48.                 if (check[ycord[0]][xcord[0]+1]==false){
  49.                 ycord.push_back(ycord[0]);
  50.         xcord.push_back(xcord[0]+1);
  51.         check[ycord[0]][xcord[0]+1]=true;
  52.                 }
  53.  
  54.      //after element
  55.         if (arr[ycord[0]][xcord[0]+1]>arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]][xcord[0]+1]))
  56.             arr[ycord[0]][xcord[0]+1]=arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]][xcord[0]+1]);
  57.         }
  58.         }
  59.    //before element
  60.         if (xcord[0]!=0&&graph[ycord[0]][xcord[0]-1]!='X'){
  61.                 if (graph[ycord[0]][xcord[0]-1]=='D'&&arr[ycord[0]][xcord[0]-1]>arr[ycord[0]][xcord[0]])arr[ycord[0]][xcord[0]-1]=arr[ycord[0]][xcord[0]];
  62.         else if (graph[ycord[0]][xcord[0]-1]!='D'){
  63.                 if (check[ycord[0]][xcord[0]-1]==false){
  64.                 ycord.push_back(ycord[0]);xcord.push_back(xcord[0]-1);
  65.                 check[ycord[0]][xcord[0]-1]=true;
  66.                 }
  67.         if (arr[ycord[0]][xcord[0]-1]>arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]][xcord[0]-1]))
  68.             arr[ycord[0]][xcord[0]-1]=arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]][xcord[0]-1]);
  69.  
  70.         }
  71.         }
  72.         // Row changing before
  73.         if (ycord[0]!=0&&graph[ycord[0]-1][xcord[0]]!='X')
  74.         {
  75.             if (graph[ycord[0]-1][xcord[0]]=='D'&&arr[ycord[0]-1][xcord[0]]>arr[ycord[0]][xcord[0]])arr[ycord[0]-1][xcord[0]]=arr[ycord[0]][xcord[0]];
  76.             else if (graph[ycord[0]-1][xcord[0]]!='D') {
  77.                     if (check[ycord[0]-1][xcord[0]]==false){
  78.             ycord.push_back(ycord[0]-1);
  79.             xcord.push_back(xcord[0]);
  80.                     check[ycord[0]-1][xcord[0]]=true;
  81.                     }
  82.  
  83.              if (arr[ycord[0]-1][xcord[0]]>arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]-1][xcord[0]]))
  84.             arr[ycord[0]-1][xcord[0]]=arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]-1][xcord[0]]);
  85.         }
  86.         }
  87.         // Row after
  88.         if (ycord[0]!=r-1&&graph[ycord[0]+1][xcord[0]]!='X')
  89.         {
  90.             if (graph[ycord[0]+1][xcord[0]]=='D'&&arr[ycord[0]+1][xcord[0]]>arr[ycord[0]][xcord[0]])arr[ycord[0]+1][xcord[0]]=arr[ycord[0]][xcord[0]];
  91.  
  92.             else if (graph[ycord[0]+1][xcord[0]]!='D') {
  93.                     if (check[ycord[0]+1][xcord[0]]==false){
  94.             ycord.push_back(ycord[0]+1);
  95.             xcord.push_back(xcord[0]);
  96.                     check[ycord[0]+1][xcord[0]]=true;
  97.                     }
  98.  
  99.              if (arr[ycord[0]+1][xcord[0]]>arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]+1][xcord[0]]))
  100.             arr[ycord[0]+1][xcord[0]]=arr[ycord[0]][xcord[0]]+mapp.find(graph[ycord[0]+1][xcord[0]]);
  101.         }
  102.         }
  103.  
  104.         ycord.pop_front();
  105.         xcord.pop_front();
  106.  
  107.  
  108.  
  109.  
  110.      }
  111.  
  112.  
  113.  
  114. cout << arr[destination.y][destination.x] << endl;
  115.  
  116.     }
  117.     return 0;
  118. }
  119.  
  120.  
  121.  
Time limit exceeded #stdin #stdout 5s 2876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sFqAvQ
language:
C++ 4.3.2 (gcc-4.3.2)
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!