fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  4. #define pb push_back
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define INF 1000000000
  8.  
  9. pii src, des;
  10. int w, h;
  11. string s[101];
  12.  
  13.  
  14. bool valid(int i, int j)
  15. {
  16.     return i >= 0 && j >= 0 && i < h && j < w && s[i][j] != '*';
  17. }
  18.  
  19. int minturns(int i, int j, char dir)
  20. {
  21.     if (!valid(i, j))
  22.         return INF;
  23.     if (des.first == i && des.second == j)
  24.         return 0;
  25.  
  26.     // going in the same direction if possible
  27.     if (dir == 'n' && valid(i - 1, j))
  28.         return minturns(i - 1, j, dir);
  29.     if (dir == 'e' && valid(i, j + 1))
  30.         return minturns(i, j + 1, dir);
  31.     if (dir == 'w' && valid(i, j - 1))
  32.         return minturns(i, j - 1, dir);
  33.     if (dir == 's' && valid(i + 1, j))
  34.         return minturns(i + 1, j, dir);
  35.  
  36.     // else change the direction
  37.     return 1 + min({
  38.         minturns(i - 1, j, 'n'),
  39.         minturns(i, j + 1, 'e'),
  40.         minturns(i, j - 1, 'w'),
  41.         minturns(i + 1, j, 's')
  42.     });;
  43. }
  44.  
  45. void test_case()
  46. {
  47.     cin >> w >> h;
  48.  
  49.     for (int i = 0; i < h; i++)
  50.         cin >> s[i];
  51.  
  52.     vector<pii> p;
  53.  
  54.     for (int i = 0; i < h; i++)
  55.         for (int j = 0; j < w; j++)
  56.             if (s[i][j] == 'C')
  57.                 p.pb({i, j});
  58.  
  59.     src = p[0], des = p[1];
  60.  
  61.     cout << min({
  62.         minturns(src.first, src.second, 'n'),
  63.         minturns(src.first, src.second, 'e'),
  64.         minturns(src.first, src.second, 'w'),
  65.         minturns(src.first, src.second, 's')
  66.     });
  67. }
  68.  
  69.  
  70. int main()
  71. {
  72.     fastio
  73.     // int t;
  74.     // cin >> t;
  75.     // while (t--)
  76.     test_case();
  77. }
  78.  
Runtime error #stdin #stdout 0s 4508KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mPaPKk
language:
C++14 (gcc 8.3)
created:
5 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!