Advertisement
Derga

Untitled

Feb 23rd, 2024
979
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct CostCoords {
  8.     int cost;
  9.     int x;
  10.     int y;
  11. };
  12.  
  13. bool operator<(const CostCoords& lhs, const CostCoords& rhs) {
  14.     return lhs.cost > rhs.cost;
  15. }
  16.  
  17. pair<int, int> GetMinCostNeighborCell(const vector<vector<int>>& costs, int x, int y) {
  18.     int new_x = x;
  19.     int new_y = y;
  20.  
  21.     for (int dx = -1; dx <= 1; ++dx) {
  22.         for (int dy = -1; dy <= 1; ++dy) {
  23.             if (dx * dx + dy * dy != 1) continue;
  24.             if (x + dx < 0 || costs.size() <= x + dx || y + dy < 0 || costs.front().size() <= y + dy) continue;
  25.  
  26.             if (costs[x + dx][y + dy] < costs[new_x][new_y]) {
  27.                 new_x = x + dx;
  28.                 new_y = y + dy;
  29.             }
  30.         }
  31.     }
  32.  
  33.     return { new_x, new_y };
  34. }
  35.  
  36. int main() {
  37.     int rows_count, cols_count, start_x, start_y, finish_x, finish_y;
  38.     cin >> rows_count >> cols_count >> start_x >> start_y >> finish_x >> finish_y;
  39.     /*
  40.     if (start_x == finish_x && start_y == finish_y) {
  41.         cout << 0;
  42.         return 0;
  43.     }
  44.     */
  45.     vector<vector<char>> map(1 + rows_count + 1, vector<char>(1 + cols_count + 1, '#'));
  46.     for (int x = 1; x <= rows_count; ++x) {
  47.         for (int y = 1; y <= cols_count; ++y) {
  48.             cin >> map[x][y];
  49.         }
  50.     }
  51.  
  52.     vector<vector<int>> costs(1 + rows_count + 1, vector<int>(1 + cols_count + 1, 1'000'000'000));
  53.    vector<vector<bool>> is_final(1 + rows_count + 1, vector<bool>(1 + cols_count + 1, false));
  54.    priority_queue<CostCoords> pq;
  55.    costs[start_x][start_y] = 0;
  56.    pq.push({ 0, start_x, start_y });
  57.    
  58.    while(!pq.empty()){
  59.        CostCoords cost_coords = pq.top();
  60.        pq.pop();
  61.        
  62.        if (is_final[cost_coords.x][cost_coords.y]) continue;
  63.        
  64.        if (cost_coords.x == finish_x && cost_coords.y == finish_y) {
  65.            cout << costs[finish_x][finish_y];
  66.            return 0;
  67.        }
  68.  
  69.        is_final[cost_coords.x][cost_coords.y] = true;
  70.        int cost = costs[cost_coords.x][cost_coords.y];
  71.        for (int dx = -1; dx <= 1; ++dx) {
  72.            for (int dy = -1; dy <= 1; ++dy) {
  73.                if (dx * dx + dy * dy != 1) continue;
  74.  
  75.                int nx = cost_coords.x + dx;
  76.                int ny = cost_coords.y + dy;
  77.                if (is_final[nx][ny]) continue;
  78.                if (map[nx][ny] == '#') continue;
  79.                
  80.                 int nd;
  81.                 if (map[cost_coords.x][cost_coords.y] == '.') {
  82.                     nd = cost + 1;
  83.                 } else if (map[cost_coords.x][cost_coords.y] == 'W') {
  84.                     nd = cost + 2;
  85.                 }
  86.                
  87.                 if (nd < costs[nx][ny]) {
  88.                     costs[nx][ny] = nd;
  89.                     pq.push({ nd, nx, ny });
  90.                 }  
  91.             }
  92.         }
  93.     }
  94.  
  95.     cout << -1;
  96.     return 0;
  97.    
  98.     /*
  99.     string path;
  100.     int x = finish_x;
  101.     int y = finish_y;
  102.     while (x != start_x || y != start_y) {
  103.         const auto& [new_x, new_y] = GetMinCostNeighborCell(costs, x, y);
  104.         if (x - new_x ==  1) path += 'S';
  105.         if (x - new_x == -1) path += 'N';
  106.         if (y - new_y ==  1) path += 'E';
  107.         if (y - new_y == -1) path += 'W';
  108.        
  109.         x = new_x;
  110.         y = new_y;
  111.     }
  112.  
  113.     reverse(begin(path), end(path));
  114.     cout << costs[finish_x][finish_y];// << '\n' << path;
  115.  
  116.     return 0;
  117.     */
  118. }
  119.  
  120. /*
  121. test1
  122. 4 8 1 1 4 8
  123. ....WWWW
  124. .######.
  125. .#..W...
  126. ...WWWW.
  127.  
  128. 13
  129. SSSEENEEEEES
  130. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement