Niloy007

Data Structure

May 31st, 2020
97
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. int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
  5. int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  6.  
  7. char grid[100][100];
  8. int visited[100][100];
  9. queue<pair<char, pair<int, int>>> blade, vampire;
  10.  
  11. bool isBlade(int i, int j) {
  12.     if (grid[i][j] == 'A' || grid[i][j] == 'B' || grid[i][j] == 'C')
  13.         return true;
  14.     else
  15.         return false;
  16. }
  17.  
  18. bool isVampire(int i, int j) {
  19.     if (grid[i][j] == 'M' || grid[i][j] == 'N' || grid[i][j] == 'O')
  20.         return true;
  21.     else
  22.         return false;
  23. }
  24.  
  25.  
  26. bool isValid(int i, int j, int row, int column) {
  27.     if (i < 0 || i >= row || j < 0 || j >= column || grid[i][j] == 'X' || grid[i][j] == '-')
  28.         return false;
  29.     else
  30.         return true;
  31. }
  32.  
  33. void bfs(pair<int, int> start, int row, int column) {
  34.     memset(visited, 0, sizeof(visited));
  35.  
  36.     queue<pair<int, int>> q;
  37.     q.push(start);
  38.  
  39.     while (!q.empty()) {
  40.         pair<int, int> top = q.front();
  41.         q.pop();
  42.  
  43.         if (grid[top.first][top.second] == 'E')
  44.             return;
  45.         else if (isBlade(top.first, top.second))
  46.             blade.push(make_pair(grid[top.first][top.second], make_pair(top.first, top.second)));
  47.         else if (isVampire(top.first, top.second))
  48.             vampire.push(make_pair(grid[top.first][top.second], make_pair(top.first, top.second)));
  49.  
  50.         if (!visited[top.first][top.second]) {
  51.             for (int i = 0; i < 4; i++) {
  52.                 int r = top.first;
  53.                 int c = top.second;
  54.  
  55.                 r += dx[i];
  56.                 c += dy[i];
  57.  
  58.                 if (isValid(r, c, row, column) && visited[r][c] == 0) {
  59.                     q.push(make_pair(r, c));
  60.                 }
  61.             }
  62.             visited[top.first][top.second] = 1;
  63.         }
  64.     }
  65. }
  66.  
  67.  
  68. int main() {
  69. #ifdef TarekHasan
  70.     freopen("input.txt", "r", stdin);
  71. #endif   // TarekHasan
  72.  
  73.     int row, column;
  74.     cin >> row >> column;
  75.  
  76.     pair<int, int> start;
  77.  
  78.     for (int i = 0; i < row; i++) {
  79.         for (int j = 0; j < column; j++) {
  80.             cin >> grid[i][j];
  81.             if (grid[i][j] == 'S')
  82.                 start = make_pair(i, j);
  83.         }
  84.     }
  85.  
  86.     bfs(start, row, column);
  87.  
  88.     cout << "Blade information: " << endl;
  89.     ;
  90.  
  91.     while (!blade.empty()) {
  92.         pair<char, pair<int, int>> top = blade.front();
  93.  
  94.         cout << top.first << " " << top.second.first << " " << top.second.second << endl;
  95.         blade.pop();
  96.     }
  97.  
  98.     cout << "Vampire information: " << endl;
  99.  
  100.     while (!vampire.empty()) {
  101.         pair<char, pair<int, int>> top = vampire.front();
  102.  
  103.         cout << top.first << " " << top.second.first << " " << top.second.second << endl;
  104.         vampire.pop();
  105.     }
  106.     return 0;
  107. }
RAW Paste Data