Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define VIS -1
  4.  
  5. using namespace std;
  6.  
  7. vector<vector<int> > grafo;
  8. vector<pair<int, int> > mov;
  9. int n, m;
  10.  
  11. void bfs(pair<int, int> dois){
  12.     int res = 0;
  13.     pair<int, int> atual, aux;
  14.     queue<pair<int, int> > fila;
  15.  
  16.     fila.push(dois);
  17.  
  18.     while(!fila.empty()){
  19.         atual = fila.front();
  20.         fila.pop();
  21.  
  22.         res++;
  23.  
  24.         if(grafo[atual.first][atual.second] == 2)
  25.             break;
  26.  
  27.         for(int i = 0; i < mov.size(); i++){
  28.             aux = make_pair(atual.first + mov[i].first, atual.second + mov[i].second);
  29.             if(aux.first >= 0 && aux.first < n && aux.second >= 0 && aux.second < m){
  30.                 if(grafo[aux.first][aux.second] == 1 || grafo[aux.first][aux.second] == 2){
  31.                     fila.push(aux);
  32.  
  33.                     if(grafo[aux.first][aux.second] == 1)
  34.                         grafo[aux.first][aux.second] = VIS;
  35.                 }
  36.             }
  37.         }
  38.     }
  39.  
  40.     printf("%d\n", res);
  41. }
  42.  
  43. int main(){
  44.     int aux;
  45.     pair<int, int> dois;
  46.  
  47.     mov.push_back(make_pair(-1, 0));
  48.     mov.push_back(make_pair(0, 1));
  49.     mov.push_back(make_pair(1, 0));
  50.     mov.push_back(make_pair(0, -1));
  51.  
  52.     scanf("%d %d", &n, &m);
  53.     grafo.assign(n, vector<int>(m, 0));
  54.  
  55.     for(int i = 0; i < n; i++){
  56.         for(int j = 0; j < m; j++){
  57.             scanf("%d", &aux);
  58.  
  59.             grafo[i][j] = aux;
  60.  
  61.             if(aux == 3)
  62.                 dois = make_pair(i, j);
  63.         }
  64.     }
  65.  
  66.     bfs(dois);
  67.  
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement