16.07.2014, 20:58. Просмотров 667. Ответов 4
Привет. Задача такая: дана клетчатая доска 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, например, думаю, что работает неправильно. Потому что в компиляторе на компьютере ответ один, на онлайн компиляторе ответ другой. Думаю, что неправильные типы у меня. Помогите.
