Advertisement
AdamTheGreat

Untitled

Sep 2nd, 2022
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. struct Point {
  7.     int x;
  8.     int y;
  9.     Point(int a, int b) {
  10.         x=a;
  11.         y=b;
  12.     }
  13. };
  14.  
  15. int main(void) {
  16.     int dirx[4] = {0, 0, -1, 1}, diry[4] = {1, -1, 0, 0};
  17.     vector<vector<int> > maze;
  18.     // vector<vector<int> > dist;
  19.     vector<vector<int> > visited;
  20.     int n, m;
  21.     cin >> n >> m;
  22.     Point friendloc = Point(0, 0), youloc = Point(0, 0);
  23.     for (int i = 0; i < n; i++) {
  24.         vector<int> temp;
  25.         for (int j = 0; j < m; j++) {
  26.             char c;
  27.             cin >> c;
  28.             if (c == '.') {
  29.                 temp.push_back(0);
  30.             } else if (c == '#') {
  31.                 temp.push_back(1);
  32.             } else if (c == 'F') {
  33.                 temp.push_back(2);
  34.                 // kfc.push_back(Point(i, j));
  35.                 // cout << "ITS A KFC!!!" << endl;
  36.             } else if (c == '@') {
  37.                 temp.push_back(0);
  38.                 youloc = Point(i, j);
  39.             } else if (c == '&') {
  40.                 temp.push_back(0);
  41.                 friendloc = Point(i, j);
  42.             } else {
  43.                 temp.push_back(c-'0');
  44.             }
  45.         }
  46.         maze.push_back(temp);
  47.     }
  48.  
  49.     vector<vector<int> > youdist;
  50.     vector<vector<int> > frienddist;
  51.  
  52.     vector<int> temp;
  53.     for (int i = 0; i < m; i++) {
  54.         temp.push_back(0);
  55.     }
  56.     for (int i = 0; i < n; i++) {
  57.         youdist.push_back(temp);
  58.         frienddist.push_back(temp);
  59.         visited.push_back(temp);
  60.     }
  61.  
  62.     queue<Point> youbook;
  63.     youbook.push(youloc);
  64.     visited[youloc.x][youloc.y] = 1;
  65.  
  66.     while(!youbook.empty()) {
  67.         Point current = youbook.front();
  68.         youbook.pop();
  69.         int nx, ny;
  70.         for(int i = 0; i < 4; i++) {
  71.             nx = current.x + dirx[i];
  72.             ny = current.y + diry[i];
  73.             if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] == 0 && maze[nx][ny] != 1) {
  74.                 visited[nx][ny] = 1;
  75.                 youdist[nx][ny] = youdist[current.x][current.y] + 1;
  76.                 youbook.push(Point(nx, ny));
  77.             }
  78.         }  
  79.     }
  80.  
  81.     if (youdist[friendloc.x][friendloc.y] == 0) {
  82.         cout << "Meeting cancelled" << endl;
  83.         return 0;
  84.     }
  85.  
  86.     for (int i = 0; i < n; i++) {
  87.         for (int j = 0; j < m; j++) {
  88.             visited[i][j] = 0;
  89.         }
  90.     }
  91.  
  92.     queue<Point> friendbook;
  93.     friendbook.push(youloc);
  94.     visited[youloc.x][youloc.y] = 1;
  95.  
  96.     while (!friendbook.empty()) {
  97.         Point current = friendbook.front();
  98.         friendbook.pop();
  99.         int nx, ny;
  100.         for(int i = 0; i < 4; i++) {
  101.             nx = current.x + dirx[i];
  102.             ny = current.y + diry[i];
  103.             if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] == 0 && maze[nx][ny] != 1) {
  104.                 visited[nx][ny] = 1;
  105.                 frienddist[nx][ny] = frienddist[current.x][current.y] + 1;
  106.                 friendbook.push(Point(nx, ny));
  107.             }
  108.         }  
  109.     }
  110.  
  111.     int least = 2147483647;
  112.     for (int i = 0; i < n; i++) {
  113.         for (int j = 0; j < m; j++) {
  114.             if (maze[i][j] == 2) {
  115.                 if (youdist[i][j] && frienddist[i][j]) {
  116.                     int dist = youdist[i][j] + frienddist[i][j];
  117.                     least = min(dist, least);
  118.                 }
  119.             }
  120.         }
  121.     }
  122.     cout << least << endl;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement