Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
#1

Неточность в понимании условия задачи "Жук" (acmp) - C++

29.07.2013, 22:37. Просмотров 863. Ответов 1
Метки нет (Все метки)

Жук
(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Петя нашел в Интернете по адресу http://buglab.ru игру-головоломку "Жук", в которой от участников требуется построить для жука лабиринт таким образом, чтобы жук как можно дольше искал выход.

Жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше. Следует заметить, что двигаясь по данному алгоритму жук всегда достигнет выхода в том случае, когда выход существует.

Изучив алгоритм движения жука Петя хочет написать программу, которая по заданному лабиринту определит количество перемещений жука прежде, чем он достигнет выхода. Помогите Пете с реализацией данной программы!

Входные данные

Входной файл INPUT.TXT в первой строке содержит разделенные пробелом целые числа N и M - количество строк и столбцов в лабиринте (4 <= N, M <= 100). Далее следует N строк, содержащих данные лабиринта построчно. Каждая строка содержит M символов - клетки лабиринта текущей строки, где символ "@" обозначает присутствие стены, а символ пробела - пустое пространство. Гарантируется, что граница лабиринта окружена стеной. Предполагается, что жук начинает свое движение из координаты (2, 2) и заканчивает в координате (M-1, N-1), подразумевается, что в этих координатах нет стен.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество движений жука, если спасительный маршрут для жука существует, и -1 в противном случае.

Примеры: INPUT.TXT OUTPUT.TXT
1 6 6
@@@@@@
@ @
@ @
@ @ @@
@ @ @
@@@@@@ 20
2 8 30
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ @ @ @@@@ @ @ @@@@ @@ @
@ @ @@ @ @ @ @ @ @ @
@ @ @ @ @@ @@ @@ @@
@ @ @ @@
@ @ @@ @ @ @@@ @ @ @ @
@ @ @ @ @ @ @@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 630
3 4 4
@@@@
@ @@
@@ @
@@@@ -1
Моё решение:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
int min(int x, int y)
{
    if (x > y)
        return y;
    else
        return x;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int N, M;
    scanf("%d %d", &N, &M);
    char a;
    scanf("%c", &a);
    int A[100][100];
 
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M+1; ++j)
        {
            scanf("%c", &a);
            if (a == '@')
                A[i][j] = 10000;
            else if (a == ' ')
                A[i][j] = 0;
        }
    int i = 1;
    int j = 1;
    A[1][1] = 0;
    int mina;
    int path;
    path = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
    {
        printf("%d ", A[i][j]);
        if (j == M-1)
            printf("\n");
    }
    while (1)
    {
        mina = min(A[i][j+1], min(A[i][j-1], min(A[i+1][j], min(A[i-1][j], A[i][j]))));
        if (mina == A[i][j])
        {
 
            A[i][j] += 1;
            printf("%d %d", i, j);
        }
        else if (mina == A[i+1][j])
        {
 
            A[i+1][j] += 1;
            printf("%d %d", i+1, j);
            ++i;
        }
        else if (mina == A[i][j+1])
        {
 
            A[i][j+1] += 1;
            printf("%d %d", i, j+1);
            ++j;
 
        }
        else if (mina == A[i-1][j])
        {
 
            A[i-1][j] += 1;
            printf("%d %d", i-1, j);
            --i;
        }
        else if (mina == A[i][j-1])
        {
 
            A[i][j-1] += 1;
            printf("%d %d", i, j-1);
            --j;
        }
        ++path;
        printf("\n");
        if (i == N-2 && j == M-2)
            break;
    }
    printf("\n %d", path);
    return 0;
}
Согласно моему решению в первом примере ответ = 12.
Его путь (клетки нумеруются от 0 до 5):
1 1
2 1
3 1
4 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3
4 4
Самое плохое, что, по моему пониманию условию, всё правильно. Однако в условии ответ = 20
Просьба указать, где я ошибся.
Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2013, 22:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Неточность в понимании условия задачи "Жук" (acmp) (C++):

Найти ошибку в решении задачи "Шифровка" (acmp) - C++
#include &lt;stdio.h&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; #include...

Ошибка в решении задачи "Судоку" (acmp) - C++
Здравствуйте. Моё решение: #include &lt;stdio.h&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;cstdio&gt; #include &lt;algorithm&gt; ...

Ошибка в понимании? или в коде? "Потоки" - C++
Здравствуйте, появилась надобность в создании потоков в программе для её ускорения, нашел на форуме рабочий код(я так думал), всё как бы оч...

Найти ошибку в решении "Числа - палиндрома" (задача с acmp) - C++
У меня WA на 4-ом тесте. #include &lt;stdio.h&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;cstdio&gt; #include &lt;algorithm&gt; ...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Задача "Выпуклая оболочка" (acmp) - C++
Вот мой код, при проверке в системе WA на 6-ом тесте. Алгоритм - найти крайние точки и построить прямоугольник по ним. #include &lt;stdio.h&gt;...

1
AntonChik
1084 / 582 / 21
Регистрация: 11.11.2008
Сообщений: 1,544
30.07.2013, 07:04 #2
ошибка в том, что после хода
2 3
жук должен сохранить направление и пойти 2 4, а не 3 3
этого в вашем алгоритме не учтено
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2013, 07:04
Привет! Вот еще темы с ответами:

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru