Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- struct CostCoords {
- int cost;
- int x;
- int y;
- };
- bool operator<(const CostCoords& lhs, const CostCoords& rhs) {
- return lhs.cost > rhs.cost;
- }
- pair<int, int> GetMinCostNeighborCell(const vector<vector<int>>& costs, int x, int y) {
- int new_x = x;
- int new_y = y;
- for (int dx = -1; dx <= 1; ++dx) {
- for (int dy = -1; dy <= 1; ++dy) {
- if (dx * dx + dy * dy != 1) continue;
- if (x + dx < 0 || costs.size() <= x + dx || y + dy < 0 || costs.front().size() <= y + dy) continue;
- if (costs[x + dx][y + dy] < costs[new_x][new_y]) {
- new_x = x + dx;
- new_y = y + dy;
- }
- }
- }
- return { new_x, new_y };
- }
- int main() {
- int rows_count, cols_count, start_x, start_y, finish_x, finish_y;
- cin >> rows_count >> cols_count >> start_x >> start_y >> finish_x >> finish_y;
- /*
- if (start_x == finish_x && start_y == finish_y) {
- cout << 0;
- return 0;
- }
- */
- vector<vector<char>> map(1 + rows_count + 1, vector<char>(1 + cols_count + 1, '#'));
- for (int x = 1; x <= rows_count; ++x) {
- for (int y = 1; y <= cols_count; ++y) {
- cin >> map[x][y];
- }
- }
- vector<vector<int>> costs(1 + rows_count + 1, vector<int>(1 + cols_count + 1, 1'000'000'000));
- vector<vector<bool>> is_final(1 + rows_count + 1, vector<bool>(1 + cols_count + 1, false));
- priority_queue<CostCoords> pq;
- costs[start_x][start_y] = 0;
- pq.push({ 0, start_x, start_y });
- while(!pq.empty()){
- CostCoords cost_coords = pq.top();
- pq.pop();
- if (is_final[cost_coords.x][cost_coords.y]) continue;
- if (cost_coords.x == finish_x && cost_coords.y == finish_y) {
- cout << costs[finish_x][finish_y];
- return 0;
- }
- is_final[cost_coords.x][cost_coords.y] = true;
- int cost = costs[cost_coords.x][cost_coords.y];
- for (int dx = -1; dx <= 1; ++dx) {
- for (int dy = -1; dy <= 1; ++dy) {
- if (dx * dx + dy * dy != 1) continue;
- int nx = cost_coords.x + dx;
- int ny = cost_coords.y + dy;
- if (is_final[nx][ny]) continue;
- if (map[nx][ny] == '#') continue;
- int nd;
- if (map[cost_coords.x][cost_coords.y] == '.') {
- nd = cost + 1;
- } else if (map[cost_coords.x][cost_coords.y] == 'W') {
- nd = cost + 2;
- }
- if (nd < costs[nx][ny]) {
- costs[nx][ny] = nd;
- pq.push({ nd, nx, ny });
- }
- }
- }
- }
- cout << -1;
- return 0;
- /*
- string path;
- int x = finish_x;
- int y = finish_y;
- while (x != start_x || y != start_y) {
- const auto& [new_x, new_y] = GetMinCostNeighborCell(costs, x, y);
- if (x - new_x == 1) path += 'S';
- if (x - new_x == -1) path += 'N';
- if (y - new_y == 1) path += 'E';
- if (y - new_y == -1) path += 'W';
- x = new_x;
- y = new_y;
- }
- reverse(begin(path), end(path));
- cout << costs[finish_x][finish_y];// << '\n' << path;
- return 0;
- */
- }
- /*
- test1
- 4 8 1 1 4 8
- ....WWWW
- .######.
- .#..W...
- ...WWWW.
- 13
- SSSEENEEEEES
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement