Advertisement
Josif_tepe

Untitled

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