ВСЕ ОТЛИЧНО
Информация о работе
Подробнее о работе
С++ https://informatics.mccme.ru/ Задача №2003. Цивилизация
- 1 страниц
- 2018 год
- 20 просмотров
- 2 покупки
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Карта мира в компьютерной игре “Цивилизация” версии 1 представляет собой прямоугольник, разбитый на квадратики. Каждый квадратик может иметь один из нескольких возможных рельефов, для простоты ограничимся тремя видами рельефов - поле, лес и вода. Поселенец перемещается по карте, при этом на перемещение в клетку, занятую полем, необходима одна единица времени, на перемещение в лес - две единицы времени, а перемещаться в клетку с водой нельзя.
У вас есть один поселенец, вы определили место, где нужно построить город, чтобы как можно скорее завладеть всем миром. Найдите маршрут переселенца, приводящий его в место строительства города, требующий минимального времени. На каждом ходе переселенец может перемещаться в клетку, имеющую общую сторону с той клеткой, где он сейчас находится.
Входные данные
Во входном файле записаны два натуральных числа N и M, не превосходящих 1000 - размеры карты мира (N - число строк в карте, M - число столбцов). Затем заданы координаты начального положения поселенца x и y, где x - номер строки, y - номер стролбца на карте (1 ≤ x ≤ N, 1 ≤ y ≤ M), строки нумеруются сверху вниз, столбцы - слева направо. Затем аналогично задаются координаты клетки, куда необходимо привести поселенца.
Далее идет описание карты мира в виде N строк, каждая из которых содержит M символов. Каждый символ может быть либо “.” (точка), обозначающим поле, либо “W”, обозначающим лес, либо “#”, обозначающим воду. Гарантируется, что начальная и конечная клетки пути переселенца не являются водой.
Выходные данные
В первой строке выходного файла выведите количество единиц времени, необходимое для перемещения поселенца (перемещение в клетку с полем занимает 1 единицу времени, перемещение в клетку с лесом - 2 единицы времени). Во второй строке выходного файла выведите последовательность символов, задающих маршрут переселенца. Каждый символ должен быть одним из четырех следующих: “N” (движение вверх), “E” (движение вправо), “S” (движение вниз), “W” (движение влево). Если таких маршрутов несколько, выведите любой из них.
Если дойти из начальной клетки в конечную невозможно, выведите число -1.
#include
#include
#include
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const long long INF = 1e10;
long long n, m, x1, x2, y1, y2, a[1009][1009], ans[1009][1009], p1[1009][1009];
char k[1009][1009];
queue qx, qy;
vector answer;
void bfs(int x3, int y3)
{
qx.push(x3);
qy.push(y3);
k[x3][y3] = 'Q';
while (!qx.empty())
{
int x = qx.front(),y = qy.front();
qx.pop();
qy.pop();
for (int i = 0; i < 4; i++)
if (a[x + dx[i]][y + dy[i]] > 0 && a[x + dx[i]][y + dy[i]] + ans[x][y] < ans[x + dx[i]][y + dy[i]])
{
qx.push(x + dx[i]);
qy.push(y + dy[i]);
p1[x + dx[i]][y + dy[i]] = 10000 * x + y;
if (dx[i] == 1 && dy[i] == 0)
k[x + dx[i]][y + dy[i]] = 'S';
if (dx[i] == -1 && dy[i] == 0)
k[x + dx[i]][y + dy[i]] = 'N';
if (dx[i] == 0 && dy[i] == 1)
k[x + dx[i]][y + dy[i]] = 'E';
if (dx[i] == 0 && dy[i] == -1)
k[x + dx[i]][y + dy[i]] = 'W';
if (a[x + dx[i]][y + dy[i]] + ans[x][y] < ans[x + dx[i]][y + dy[i]])
ans[x + dx[i]][y + dy[i]] = a[x + dx[i]][y + dy[i]] + ans[x][y];
}
}
}
int main()
{
cin >> n >> m >> x1 >> y1 >> x2 >> y2;
for (int i = 1; i x;
ans[i][j] = INF;
if (x == '.')
a[i][j] = 1;
if (x == 'W')
a[i][j] = 2;
}
ans[x1][y1] = 0;
bfs(x1, y1);
if (ans[x2][y2] != INF)
{
cout
Задача №2003. Цивилизация
Карта мира в компьютерной игре “Цивилизация” версии 1 представляет собой прямоугольник, разбитый на квадратики. Каждый квадратик может иметь один из нескольких возможных рельефов, для простоты ограничимся тремя видами рельефов - поле, лес и вода. Поселенец перемещается по карте, при этом на перемещение в клетку, занятую полем, необходима одна единица времени, на перемещение в лес - две единицы времени, а перемещаться в клетку с водой нельзя.
У вас есть один поселенец, вы определили место, где нужно построить город, чтобы как можно скорее завладеть всем миром. Найдите маршрут переселенца, приводящий его в место строительства города, требующий минимального времени. На каждом ходе переселенец может перемещаться в клетку, имеющую общую сторону с той клеткой, где он сейчас находится.
Входные данные
Во входном файле записаны два натуральных числа N и M, не превосходящих 1000 - размеры карты мира (N - число строк в карте, M - число столбцов). Затем заданы координаты начального положения поселенца x и y, где x - номер строки, y - номер стролбца на карте (1 ≤ x ≤ N, 1 ≤ y ≤ M), строки нумеруются сверху вниз, столбцы - слева направо. Затем аналогично задаются координаты клетки, куда необходимо привести поселенца.
Далее идет описание карты мира в виде N строк, каждая из которых содержит M символов. Каждый символ может быть либо “.” (точка), обозначающим поле, либо “W”, обозначающим лес, либо “#”, обозначающим воду. Гарантируется, что начальная и конечная клетки пути переселенца не являются водой.
Выходные данные
В первой строке выходного файла выведите количество единиц времени, необходимое для перемещения поселенца (перемещение в клетку с полем занимает 1 единицу времени, перемещение в клетку с лесом - 2 единицы времени). Во второй строке выходного файла выведите последовательность символов, задающих маршрут переселенца. Каждый символ должен быть одним из четырех следующих: “N” (движение вверх), “E” (движение вправо), “S” (движение вниз), “W” (движение влево). Если таких маршрутов несколько, выведите любой из них.
Если дойти из начальной клетки в конечную невозможно, выведите число -1.
https://informatics.mccme.ru/
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
