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

Клетчатая доска - Определить количество способов добраться до последней клетки N-M - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Не работает функция sort (vector, vector) http://www.cyberforum.ru/cpp-beginners/thread1228298.html
#include <iostream> #include <conio.h> #include <vector> #include <string> #include <algorithm> using namespace std; class Name_pairs { private:
C++ Написать функцию вычисления произведения отрицательных чисел для трех целых аргументов Написать функцию вычисления произведения отрицательных чисел для трех целых аргументов. Написать операторы вызова функции, с помощью которых определяется и выводится на экран произведение отрицательных чисел для следующих входных данных: a) k, r, y; b) 3, -4, k. http://www.cyberforum.ru/cpp-beginners/thread1228284.html
C++ Равномерное дополнение строки пробелами
Всем доброго времени суток.Имеется задача: Дан текст из нескольких строк. Написать функцию, равномерно дополняющую строку пробелами до определенной длины и с ее помощью отформатировать этот текст. В программе должны быть функции - ввода текста (из нескольких строк); - вывода текста на экран; - форматирования строки текста в соответствии с заданием. Подскажите КАК следует понимать условие...
Указатели на функции (Прата) - не пойму, как это работает C++
Стивен Прата "Язык программирования C++. Лекции и упражнения" 7 глава, стр. 355, листинг 7.18. fun_ptr.cpp // fun_ptr.cpp -- pointers to functions #include <iostream> double betsy(int); double pam(int); // second argument is pointer to a type double function that
C++ Как ограничить поле ввода только одним символом? А двумя? http://www.cyberforum.ru/cpp-beginners/thread1228219.html
Как ограничить поле ввода только одним символом? А двумя? Например чтобы сразу после нажатия клавиши(двух), программа переходила к следующей операции, не ожидая нажатия "ентер", либо же не давала ввести символов больше положенного? Как сделать так, чтобы можно было напечатать в строку ввода только определённые символы, например y/n? Спасибо.
C++ Невозможно запустить программу. Отсутствует libiconv-2.dll Запуск программы невозможен так как на компьютере отсутствует libiconv-2.dll.попробуйте переустановить программу Добавлено через 36 секунд Что нужно сделать? подробнее

Показать сообщение отдельно
thejadefalcon
 Аватар для thejadefalcon
0 / 0 / 0
Регистрация: 23.09.2013
Сообщений: 41
16.07.2014, 20:58     Клетчатая доска - Определить количество способов добраться до последней клетки N-M
Привет. Задача такая: дана клетчатая доска NxM (-1000 <= N,M <= 1000), мы находимся в самой первой клетке 1-1. Нужно определить количество способов добраться до последней клетки N-M. Можно двигаться только вправо и вниз, также на доске существуют препятствия с известными координатами, через них пройти нельзя. Входные данные (Пример):
3 3 - размеры доски
1 - кол-во преград
2 2 - координаты преграды

Так как в конце может получиться большое число, требуют в ответе написать остаток от деления на 1000000007.

В общем-то я сделал: http://ideone.com/3N8Nsk

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
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
#include <iostream>
 
using namespace std;
 
bool barrier(int i, int j, int **Arr, int n) { // Функция проверяет преграда ячейка или нет
    for (int k = 0; k < n; k++) {
        if (i == Arr[k][0]-1 && j == Arr[k][1]-1) {
            return true;
        }
    }
    return false;
}
 
int main() {
    int n,m,k;
    int row = 0;
    int col = 0;
    cin >> n >> m; // Размер клеточной доски
        
    unsigned long **possible = new unsigned long* [n]; 
    for (int i = 0; i < n; i++)
        possible[i] = new unsigned long [m]; 
 
    cin >> k; // Количество преград
 
    int **Arr = new int* [2]; 
    for (int i = 0; i < k; i++)
        Arr[i] = new int [2]; 
 
    if (k > 0) {
        for (int i = 0; i < k; i++) { // Заносим координаты преград
            for (int j = 0; j < 2; j++) {
                cin >> Arr[i][j];
            }
        }
    }
    
    possible[row][col] = 1;
    bool start = false;
 
    for (int i = 0; i < n; i++) { // Считаем для каждой ячейки - сколькими способами можно до нее добраться
        for (int j = 0; j < m; j++) {
            if (barrier(i, j, Arr, k)) { // Если ячейка преграда, делаем кол-во способов добраться до нее 0, чтобы дальнейшие ячейки не могли иметь путь через нее
                possible[i][j] = 0;
                continue;
            }
            if (start) {
                if (i == 0) {
                    possible[i][j] = possible[i][j-1]; // Если ячейки из верхней строчки, то можем попасть в нее только с левой ячейки, получаем из нее коли-чество способов добраться
                    continue;
                }
                if (j == 0) { // Если ячейка из левого столбика, то можем попасть в нее только сверху, получаем из нее коли-чество способов добраться
                    possible[i][j] = possible[i-1][j];
                    continue;
                }
                possible[i][j] = possible[i][j-1] + possible[i-1][j]; // В иных случаях прибавляем кол-во способов добраться из верхней ячейки и левой
            }
            else {
                start = true;
            }
        }
    }
 
    cout << possible[n-1][m-1]%1000000007; // Выводим остаток от деления на 1000000007
    
    return 0;
}
Для простых тестовых примеров работает, а вот для БОЛЬШИХ тестовых примеров 1000х1000, например, думаю, что работает неправильно. Потому что в компиляторе на компьютере ответ один, на онлайн компиляторе ответ другой. Думаю, что неправильные типы у меня. Помогите.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru