Advertisement
Josif_tepe

Untitled

Jun 8th, 2024
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. int n, m;
  7. char mat[105][105];
  8. int bfs(int si, int sj, int ei, int ej) {
  9.   queue<int> q;
  10.   q.push(si);
  11.   q.push(sj);
  12.   q.push(0);
  13.  
  14.   vector<vector<bool>> visited(n, vector<bool>(m, false));
  15.   visited[si][sj] = true;
  16.   int di[] = {-1, 1, 0, 0};
  17.   int dj[] = {0, 0, -1, 1};
  18.   while(!q.empty()) {
  19.     int ci = q.front();
  20.     q.pop();
  21.     int cj = q.front();
  22.     q.pop();
  23.     int cekor = q.front();
  24.     q.pop();
  25.  
  26.     if(ci == ei and cj == ej) {
  27.       return cekor;
  28.     }
  29.     for(int i = 0; i < 4; i++) {
  30.       int ti = ci + di[i];
  31.       int tj = cj + dj[i];
  32.       if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#'){
  33.         q.push(ti);
  34.         q.push(tj);
  35.         q.push(cekor + 1);
  36.         visited[ti][tj] = true;
  37.  
  38.       }
  39.     }
  40.  
  41.   }
  42. }
  43. int main()
  44. {
  45.   cin >> n >> m;
  46.   vector<pair<int, int>> drinks;
  47.   int si = 0, sj = 0, bi = 0, bj = 0;
  48.   for(int i = 0; i < n; i++) {
  49.     for(int j = 0; j < m; j++) {
  50.       cin >> mat[i][j];
  51.       if(mat[i][j] == 'D') {
  52.         drinks.push_back(make_pair(i, j));
  53.       }
  54.       if(mat[i][j] == 'S') {
  55.         si = i;
  56.         sj = j;
  57.       }
  58.       if(mat[i][j] == 'B') {
  59.         bi = i;
  60.         bj = j;
  61.       }
  62.     }
  63.   }
  64.   vector<int> permutacija;
  65.   for(int i = 0; i < drinks.size(); i++) {
  66.     permutacija.push_back(i);
  67.   }
  68.   int sz = permutacija.size();
  69.  
  70.   int res = 1000;
  71.   do {
  72.     int path = 0;
  73.     for(int i = 0; i < permutacija.size(); i++) {
  74.       if(i == 0) {
  75.         path += bfs(si, sj, drinks[permutacija[i]].first, drinks[permutacija[i]].second);
  76.       }
  77.       else {
  78.         path += bfs(drinks[permutacija[i]].first, drinks[permutacija[i]].second, drinks[permutacija[i - 1]].first, drinks[permutacija[i - 1]].second);
  79.       }
  80.     }
  81.     path += bfs(drinks[permutacija[sz - 1]].first, drinks[permutacija[sz - 1]].second, bi, bj);
  82.   res = min(res ,path);
  83.   } while(next_permutation(permutacija.begin(), permutacija.end()));
  84.   cout << res << endl;
  85.     return 0;
  86. }
  87.  /*
  88. CX..
  89. C...
  90.  
  91. K = 2
  92.  
  93.  
  94.  **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement