fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 105
  3. using namespace std;
  4. struct node
  5. {
  6.         int u ;
  7.         int v ;
  8.         int hp ;
  9. };
  10. int MinDist[NMAX][NMAX][5];
  11. bool visited[NMAX][NMAX][5];
  12. int dx[] = { -1 , 0 , 0 , 1};
  13. int dy[] = { 0 , -1 , 1 , 0};
  14.  
  15. int row , colum;
  16. char Maze[NMAX][NMAX];
  17. node Start , End;
  18.  
  19. void enter()
  20. {
  21.         cin>> row >>colum;
  22.         for(int i = 1 ; i <=  row ; i++)
  23.         {
  24.                 string s;
  25.                 cin>>s;
  26.                 for(int j = 1 ; j <= colum ; j++)
  27.                 {
  28.                         Maze[i][j] = s[j-1];
  29.  
  30.                         if(s[j-1] == 'S')
  31.                         {
  32.                                 Start = { i , j , 3};
  33.                         }
  34.  
  35.                         if(s[j-1] == 'D')
  36.                         {
  37.                                 End = {i , j , 0};
  38.                         }
  39.                 }
  40.         }
  41. }
  42.  
  43. void BFS()
  44. {
  45.         deque<node> de;
  46.         de.push_back(Start);
  47.         visited[Start.u][Start.v][Start.hp] = true;
  48.  
  49.         while(!de.empty())
  50.         {
  51.                 node top = de.front();
  52.                 de.pop_front();
  53.  
  54.                 int i = top.u;
  55.                 int j = top.v;
  56.  
  57.                 for(int k = 0 ; k  <= 3 ; k++)
  58.                 {
  59.                         int u = i + dx[k];
  60.                         int v = j + dy[k];
  61.                         int hp = top.hp;
  62.  
  63.  
  64.                         if( 1 <= u && u <= row && 1 <= v && v <= colum)
  65.                         {
  66.                                 if(Maze[u][v] == '+')   --hp;
  67.  
  68.                                 if(hp <= 0)  continue;
  69.  
  70.                                 if( !visited[u][v][hp])
  71.                                 {
  72.                                         visited[u][v][hp]  = true;
  73.                                         MinDist[u][v][hp]  = MinDist[i][j][top.hp] + 1;
  74.                                         de.push_back({u,v,hp});
  75.  
  76.                                 }
  77.                         }
  78.                 }
  79.         }
  80. }
  81. void process()
  82. {
  83.         BFS();
  84.         int ans = INT_MAX;
  85.  
  86.         for(int hp = 1; hp <= 3; hp++)   if(MinDist[End.u][End.v][hp])   ans = min(ans , MinDist[End.u][End.v][hp]);
  87.  
  88.         cout<< ((ans == INT_MAX) ?-1:ans) ;
  89. }
  90. int main()
  91. {
  92.     ios_base::sync_with_stdio(0);
  93.     cin.tie(nullptr);
  94.     cout.tie(nullptr);
  95.     enter();
  96.     process();
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/8KR96o
language:
C++14 (gcc 8.3)
created:
59 days 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!