fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. int main() {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(NULL);
  8. #ifndef ONLINE_JUDGE
  9.     freopen("input.txt" , "r" , stdin);
  10.     freopen("output.txt" , "w" , stdout);
  11. #endif
  12.     ll n, m, k;
  13.     cin >> n >> m >> k;
  14.     vector<string> mat(n);
  15.     vector<ll> start, end;
  16.     for (ll i = 0; i < n; i++) {
  17.         string s = "";
  18.         for (ll j = 0; j < m; j++) {
  19.             char c;
  20.             cin >> c;
  21.             s += c;
  22.             if (c == 'S') {
  23.                 start = {i, j};
  24.             }
  25.             if (c == 'G') {
  26.                 end = {i, j};
  27.             }
  28.         }
  29.         mat[i] = s;
  30.     }
  31.  
  32.     vector<vector<ll>> dis(n, vector<ll>(m, 1e9));
  33.     vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));
  34.  
  35.     dis[start[0]][start[1]] = 0;
  36.     vis[start[0]][start[1]][k] = true;
  37.     queue<pair<pair<ll, ll>, ll>> q;
  38.     q.push({{start[0], start[1]}, k});
  39.  
  40.     while (!q.empty()) {
  41.         auto v = q.front();
  42.         q.pop();
  43.         ll x = v.first.first;
  44.         ll y = v.first.second;
  45.         ll remaining = v.second;
  46.         if(x == end[0] && y == end[1]){
  47.           break;
  48.         }
  49.         vector<vector<ll>> dir{{1, 0}, {0, 1}, { -1, 0}, {0, -1}};
  50.  
  51.         for (auto it : dir) {
  52.             ll a = x + it[0];
  53.             ll b = y + it[1];
  54.             if (a >= 0 && b >= 0 && a < n && b < m && !vis[a][b][remaining]) {
  55.                 if (mat[a][b] == '#') {
  56.                     if (remaining > 0) {
  57.                         dis[a][b] = min(dis[a][b], 1 + dis[x][y]);
  58.                         q.push({{a, b}, remaining - 1});
  59.                         vis[a][b][remaining - 1] = true;
  60.                     }
  61.                 } else {
  62.                     dis[a][b] = min(dis[a][b], 1 + dis[x][y]);
  63.                     q.push({{a, b}, remaining});
  64.                     vis[a][b][remaining] = true;
  65.                 }
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout << (dis[end[0]][end[1]] == 1e9 ? -1 : dis[end[0]][end[1]]) << '\n';
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
4 5 13
#####
S#...
.#.#.
...#G
stdout
copy 
6
https://ideone.com/Quy8aK
language:
C++14 (gcc 8.3)
created:
10 days 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!