fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Fast_IO                       \
  6.     ios_base::sync_with_stdio(false); \
  7.     cin.tie(NULL);                    \
  8.     cout.tie(NULL);
  9. #define int long long int
  10. #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  11.  
  12. const int MOD = 998244353;
  13. const int bigMOD = 1e9+7;
  14.  
  15. /*************** My code start here ****************/
  16.  
  17. int32_t main()
  18. {
  19.     Fast_IO
  20. #ifndef ONLINE_JUDGE
  21.         freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23. #endif
  24.     clock_t danger_close = clock();
  25.     int t = 1;
  26.     // cin >> t;
  27.     while (t--)
  28.     {
  29.         int n, m, X, Y, d = 0, cnt = 0, f = 0;
  30.         cin >> n >> m >> X >> Y;
  31.         vector<string> grid(n);
  32.         vector<pair<int, int>> coins;
  33.         map<pair<int, int>, int> mp;
  34.         for(int i = 0; i < n; i++) {
  35.             cin >> grid[i];
  36.             for(int j = 0; j < m; j++) {
  37.                 if(grid[i][j] == 'C')
  38.                     mp[{i, j}] = cnt++;
  39.             }
  40.         }
  41.         queue<tuple<int, int, int>> q;
  42.         q.push({0, 0, 0});
  43.         vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  44.         vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(m, vector<bool>(1 << cnt, false)));
  45.         vis[0][0][0] = true;
  46.         while(!q.empty()) {
  47.             int l = q.size();
  48.             d++;
  49.             while(l--) {
  50.                 auto [x, y, mask] = q.front();
  51.                 q.pop();
  52.                 for(auto [dx, dy]: dirs) {
  53.                     int nx = x+dx, ny = y+dy;
  54.                     if(nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == '#')
  55.                         continue;
  56.                     if(mask == (1<<cnt)-1 and nx == X and ny == Y) {
  57.                         f = 1;
  58.                         break;
  59.                     }
  60.                     int newmask = mask;
  61.                     if(grid[nx][ny] == 'C')
  62.                         newmask = mask | (1<<mp[{nx, ny}]);
  63.                     if(vis[nx][ny][newmask])
  64.                         continue;
  65.                     q.push({nx, ny, newmask});
  66.                     vis[nx][ny][newmask] = true;
  67.                 }
  68.             }
  69.             if(f)
  70.                 break;
  71.         }
  72.         if(f)
  73.             cout << d << '\n';
  74.         else
  75.             cout << -1 << '\n';
  76.     }
  77.     debug("Total Time: %.3f\n", (double)(clock() - danger_close) / CLOCKS_PER_SEC);
  78.     return 0;
  79. }
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
5 6 4 5
......
.C#...
..#C..
...#..
...C..
stdout
copy 
13
stderr
copy 
Total Time: 0.000
https://ideone.com/Hoc6qc
language:
C++14 (gcc 8.3)
created:
1 day 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!