Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
29.07.2013, 22:37     Неточность в понимании условия задачи "Жук" (acmp) #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
Просьба указать, где я ошибся.
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2013, 22:37     Неточность в понимании условия задачи "Жук" (acmp)
Посмотрите здесь:

C++ Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой или одним из знаков "+", "-", "*".
Условия "если", "то" C++
Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений: "Рабочий день","Суббота" или "Воскресенье" C++
C++ Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей";
C++ Написать программу которaя запрашиваeт у пользователя номер дня недели, затем выводит одно из сообщений "рабочий день", "суббота", "воскресенье"
C++ Как отключить автоматическое добавление "_" "@" "number" к имени экстернального метода?
На C++ в строке после символа - "+" поставить символ "*" и посчитать сколько "+" C++
Visual Studio не читает операторы, что начинаются на "glu" ("gluBuild2DMipmaps", "gluPerspective") C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AntonChik
1083 / 581 / 21
Регистрация: 11.11.2008
Сообщений: 1,544
30.07.2013, 07:04     Неточность в понимании условия задачи "Жук" (acmp) #2
ошибка в том, что после хода
2 3
жук должен сохранить направление и пойти 2 4, а не 3 3
этого в вашем алгоритме не учтено
Yandex
Объявления
30.07.2013, 07:04     Неточность в понимании условия задачи "Жук" (acmp)
Ответ Создать тему
Опции темы

Текущее время: 18:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru