Advertisement
Josif_tepe

Untitled

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