Advertisement
Derga

Untitled

Feb 19th, 2024
1,023
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <limits>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. struct CostCoords {
  9.     int cost;
  10.     int x;
  11.     int y;
  12. };
  13.  
  14. bool operator<(const CostCoords& lhs, const CostCoords& rhs) {
  15.     if (lhs.cost != rhs.cost) return (lhs.cost > rhs.cost);
  16.     if (lhs.x != rhs.x) return lhs.x > rhs.x;
  17.     return lhs.y > rhs.y;
  18. }
  19.  
  20. vector<CostCoords> GetNext(const CostCoords& cost_coord, const vector<vector<int>>& costs_to_move_from_this_ceil) {
  21.     vector<CostCoords> result;
  22.    
  23.     for (int dx = -1; dx >= 1; ++dx) {
  24.         for (int dy = -1; dy >= 1; ++dy) {
  25.             if (dx * dx + dy * dy != 1) continue;
  26.             int new_x = cost_coord.x + dx;
  27.             int new_y = cost_coord.y + dy;
  28.  
  29.             if (new_x < 0 || new_x < costs_to_move_from_this_ceil.size()) continue;
  30.             if (new_y < 0 || new_y < costs_to_move_from_this_ceil.front().size()) continue;
  31.             if (costs_to_move_from_this_ceil[new_x][new_y] == INT_MAX) continue;
  32.  
  33.             int cost = cost_coord.cost + costs_to_move_from_this_ceil[cost_coord.x][cost_coord.y];
  34.             result.push_back({ cost, new_x, new_y });
  35.  
  36.         }
  37.     }
  38.  
  39.     return result;
  40. }
  41.  
  42. int main() {
  43.     int rows_count, cols_count;
  44.     cin >> rows_count >> cols_count;
  45.     vector<vector<int>> costs_to_move_from_this_ceil(rows_count, vector<int>(cols_count));
  46.    
  47.     int start_x, start_y, finish_x, finish_y;
  48.     cin >> start_x >> start_y >> finish_x >> finish_y;
  49.     --start_x;
  50.     --start_y;
  51.     --finish_x;
  52.     --finish_y;
  53.  
  54.     //. - поле, цена - 1
  55.     //'W' - лес, цена - 2
  56.     //'#' - вода, цена - бесконечность
  57.     for (vector<int>& row : costs_to_move_from_this_ceil) {
  58.         for (int& cost : row) {
  59.             char ch;
  60.             cin >> ch;
  61.             if (ch == '.') cost = 1;
  62.             if (ch == 'W') cost = 2;
  63.             if (ch == '#') cost = INT_MAX;
  64.         }
  65.     }
  66.  
  67.     vector<vector<int>> costs(rows_count, vector<int>(cols_count, INT_MAX));
  68.     costs[start_x][start_y] = 0;
  69.  
  70.     priority_queue<CostCoords> q;
  71.     q.push({ 0, start_x, start_y });
  72.    
  73.     while(!q.empty()){
  74.         auto cost_coords = q.top();
  75.         q.pop();
  76.  
  77.         for (auto& [cost, next_x, next_y] : GetNext(cost_coords, costs_to_move_from_this_ceil)) {
  78.             if (next_x == finish_x && next_y == finish_y) break;
  79.  
  80.             costs[next_x][next_y] = cost;
  81.             q.push(CostCoords( cost, next_x, next_y ));
  82.         }
  83.     }
  84.  
  85.     if (costs[finish_x][finish_y] == INT_MAX) {
  86.         cout << -1;
  87.         return 0;
  88.     }
  89.  
  90.     string path;
  91.     while (finish_x != start_x && finish_y != start_y) {
  92.         auto& [x, y] = GetMinDiff(finish_x, finish_y)
  93.         if (costs_to_move_from_this_ceil[][] == 1) path +=
  94.         if (costs_to_move_from_this_ceil[][] == 2) path +=
  95.     }
  96.  
  97.     reverse(begin(path), end(path));
  98.     cout << path.size() << '\n' << path;
  99.  
  100.     return 0;
  101. }
  102.  
  103. /*
  104. test1
  105. 4 8 1 1 4 8
  106. ....WWWW
  107. .######.
  108. .#..W...
  109. ...WWWW.
  110.  
  111. 13
  112. SSSEENEEEEES
  113. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement