mickypinata

PROG-T1037: Slikar

Jun 22nd, 2021
637
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> pii;
  5.  
  6. enum type {
  7.     WATER = 0, HERO = 1
  8. };
  9.  
  10. const int N = 50;
  11.  
  12. pii dir[4] = {pii(1, 0), pii(0, 1), pii(-1, 0), pii(0, -1)};
  13. char board[N + 10][N + 10];
  14. int row, col;
  15.  
  16. bool isInBoard(int r, int c){
  17.     return r >= 1 && r <= row && c >= 1 && c <= col;
  18. }
  19.  
  20. int main(){
  21.  
  22.     pii st, ed;
  23.     scanf("%d%d", &row, &col);
  24.     queue<pair<type, pii>> que;
  25.     for(int i = 1; i <= row; ++i){
  26.         for(int j = 1; j <= col; ++j){
  27.             scanf(" %c", &board[i][j]);
  28.             if(board[i][j] == 'S'){
  29.                 st = pii(i, j);
  30.                 board[i][j] = '.';
  31.             } else if(board[i][j] == 'D'){
  32.                 ed = pii(i, j);
  33.             } else if(board[i][j] == '*'){
  34.                 que.emplace(WATER, pii(i, j));
  35.                 board[i][j] = 'X';
  36.             }
  37.         }
  38.     }
  39.  
  40.     vector<vector<int>> dist(row + 1, vector<int>(col + 1, -1));
  41.     dist[st.first][st.second] = 0;
  42.     que.emplace(HERO, st);
  43.     while(!que.empty()){
  44.         type t = que.front().first;
  45.         pii p = que.front().second;
  46.         int ur = p.first;
  47.         int uc = p.second;
  48.         que.pop();
  49.         if(t == HERO && ur == ed.first && uc == ed.second){
  50.             cout << dist[ur][uc];
  51.             return 0;
  52.         }
  53.         for(int d = 0; d <= 3; ++d){
  54.             int vr = ur + dir[d].first;
  55.             int vc = uc + dir[d].second;
  56.             if(isInBoard(vr, vc)){
  57.                 if(t == WATER && board[vr][vc] == '.'){
  58.                     board[vr][vc] = 'X';
  59.                     que.emplace(WATER, pii(vr, vc));
  60.                 } else if(t == HERO && board[vr][vc] != 'X' && dist[vr][vc] == -1){
  61.                     dist[vr][vc] = dist[ur][uc] + 1;
  62.                     que.emplace(HERO, pii(vr, vc));
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     cout << "KAKTUS";
  68.  
  69.     return 0;
  70. }
  71.  
RAW Paste Data