-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
1

Найти счётчик

11.12.2019, 21:21. Показов 837. Ответов 11
Метки c++ (Все метки)

Приветствую! Наткнулся на такую задачу:
Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.
Формат входных данных
Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
Формат выходных данных
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.
Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример
Входные данные
3 5
11111
10101
11111
Выходные данные
3
Входные данные
3 5
11101
10101
10111
Выходные данные
impossible
И такое решение:
C++
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
#include <iostream>
#include <vector>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    
    std::vector< std::vector< int > > matrix(n, std::vector< int > (m) );
    matrix[0][0] = 1;
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            int x;
            std::cin >> x;
            if ( x != 0 )
            {
                if ( i != 0 )
                    matrix[i][j] += matrix[i - 1][j];
                    
                if ( j != 0 )
                    matrix[i][j] += matrix[i][j - 1];
            }
        }
    }
    
    int count = matrix[n - 1][m - 1];   
    if ( count == 0 )
        std::cout << "Impossible";
    else
        std::cout << count;
}
Но у меня есть вопросик: проходящих через M+N-1 комнату. Это ведь своеобразный ограничитель? То есть больше 7 (для примера в условии) он не пройдет, так? Если да, то где и как можно заменить, чтобы этот счётчик был const, например, задавался изначально?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2019, 21:21
Ответы с готовыми решениями:

Реализовать класс "Счётчик" (Найти и исправить ошибки в коде)
Вот условие: &quot;Цифровой счетчик, это переменная с ограниченным диапазоном. Значение которой...

Создать класс «счетчик», реализующий циклический счетчик, со следующей структурой
Создать класс «счетчик», реализующий циклический счетчик, со следующей структурой: -поле состояния...

Счетчик - найти среднее арифметическое
у меня вот проблема...среднее арифметическое находится неправильно.не пойму в чем дело.может...

Где найти счетчик без скриптов?
Хотела на ЖЖ поставить счетчик, но у них в FAQ написано, что это возможно только, если он не...

11
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
11.12.2019, 23:20 2
Он только и может сделать M+N-1 шагов до цели, не больше и не меньше. Нет смысла хранить это число.
0
-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
12.12.2019, 08:16  [ТС] 3
Хорошо, пойдем по-другому, как можно в эту программу вклинить счётчик, чтобы он не мог пройти больше, например, S клеток?
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
12.12.2019, 10:02 4
В этот код счётчик ходов не добавить, т.к. никто никуда не ходит. Тут для каждой клетки сохраняют число вариантов на неё попасть с двух других.
Кстати, код немного разнится с условием, разные начальная\конечная клетки.
0
-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
12.12.2019, 10:08  [ТС] 5
Что? Разве?
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
12.12.2019, 10:16 6
Цитата Сообщение от Keberson Посмотреть сообщение
Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
Цитата Сообщение от Keberson Посмотреть сообщение
for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            int x;
            std::cin >> x;
            if ( x != 0 )
            {
                if ( i != 0 )
                    matrix[i][j] += matrix[i - 1][j];
if ( j != 0 )
                    matrix[i][j] += matrix[i][j - 1];
            }
Обходить матрицу надо бы начинать со старта (там как-раз единичка). А матрицу в этом коде заполняют сразу, с нулевого индекса (слева направо, сверху вниз построчно).
Тут ещё считывают оператором >>, а по условию матрица без пробелов.
0
-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
12.12.2019, 10:25  [ТС] 7
Да, да, да... Видел это, я начал писать код на основе этого и исправил эти проблемы: меняю местами строки и вуаля; вторая проблема тоже решена, я поэтому делаю больше акцент на том, как установить туда счётчик ( как я понимаю, это не получится сделать и нужно писать другой код?

Добавлено через 3 минуты
У меня есть вариант установить счётчик после:
C++
1
If (x != 0)
А после значение разделить на число, которое отвечает за максимальное количество клеток, которое можно пройти
Как думаете, правильно ли?
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
12.12.2019, 10:58 8
Keberson, не подскажу, т.к. до сих пор не понял, как тут должен работать счётчик. Вот в цикле начинается обход всей матрицы построчно. В какой именно момент вы хотите прервать обход? На каком-то расстоянии не дальше N шагов от старта? Ну урежте m и n, только смысл какой?

Добавлено через 26 минут
На всякий случай скажу ещё раз, что любой путь до финиша займёт ровно m+n-1 шагов, т.к. путь лежит из одного угла в противоположный. Если будет матрица из одних единиц, то все клетки будут задействованы под пути и длина у них будет одна (ведь по условию он может шагать только в сторону финиша, значит и варианты наступить на клетку подсчитываются суммой вариантов только с двух предыдущих). Никаких лишних расчётов нету и оптимизировать тут нечего.
0
-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
12.12.2019, 11:14  [ТС] 9
Я это прекрасно понимаю, но если я захочу задать изначально задавать, например, не 7 (для данного случая), а 6, то как быть? В эту прогу никак не вставишь, получается(

Добавлено через 5 минут
Прерывать обход не надо, он считает и потом возможно что-то с ним сделать
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
12.12.2019, 11:19 10
Тут и 7 нигде явно не задаётся, так получается после запрета двигаться в другую сторону от финиша (влево и вниз).
0
-1 / 0 / 0
Регистрация: 07.12.2019
Сообщений: 25
12.12.2019, 11:34  [ТС] 11
Нет нет нет нет нет, неправильно меня понимаете, я хочу ввести ограничение на передвижение, то есть, например, не больше 7 клеток
0
817 / 504 / 211
Регистрация: 19.01.2019
Сообщений: 1,196
12.12.2019, 12:05 12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    //матрица из единиц
    1 2 3
    4 5 6
    7 8 9
    a b c
 
    //результат обхода
    1 4 10
    1 3 6       
    1 2 3       
    1 1 1       
 
    //возможные пути
    a74123
    a74523
    a74563
    a78523
    a78563
    a78963
    ab8523
    ab8563
    ab8963
    abc963
Ограничить шаги значит не дать ему наступить на последние клетки из списка возможных путей?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.12.2019, 12:05
Помогаю со студенческими работами здесь

Где найти счетчик реальной посещаемости сайта
Здравствуйте! У меня на сайте стоит счетчик от Рамблера, все как полагается скрытый счетчик в...

Найти вероятность того, что в счётчик не попадёт ни одной частицы
Вероятность попадения частицы в счётчик Гейгера за малое t равна at и не зависит от того, сколько...

Необходимо найти счетчик (или просто набор чисел) для сайта
Здравствуйте. Итак, мне необходимо поставить счетчик на сайт, чтобы это число росло с...

Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик глубины рекурсии WG)
помоги, пожалуйста, нужна программа:wall: Для графа дерева найти длину пути от вершины U до V ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru