fork(2) download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. bool barrier(int i, int j, int **Arr, int n) { // Функция проверяет преграда ячейка или нет
  6. 	for (int k = 0; k < n; k++) {
  7. 		if (i == Arr[k][0]-1 && j == Arr[k][1]-1) {
  8. 			return true;
  9. 		}
  10. 	}
  11. 	return false;
  12. }
  13.  
  14. int main() {
  15. 	int n,m,k;
  16. 	int row = 0;
  17. 	int col = 0;
  18. 	cin >> n >> m; // Размер клеточной доски
  19.  
  20. 	unsigned long **possible = new unsigned long* [n]; 
  21.     for (int i = 0; i < n; i++)
  22.         possible[i] = new unsigned long [m]; 
  23.  
  24. 	cin >> k; // Количество преград
  25.  
  26. 	int **Arr = new int* [2]; 
  27.     for (int i = 0; i < k; i++)
  28.         Arr[i] = new int [2]; 
  29.  
  30. 	if (k > 0) {
  31. 		for (int i = 0; i < k; i++) { // Заносим координаты преград
  32. 			for (int j = 0; j < 2; j++) {
  33. 				cin >> Arr[i][j];
  34. 			}
  35. 		}
  36. 	}
  37.  
  38. 	possible[row][col] = 1;
  39. 	bool start = false;
  40.  
  41. 	for (int i = 0; i < n; i++) { // Считаем для каждой ячейки - сколькими способами можно до нее добраться
  42. 		for (int j = 0; j < m; j++) {
  43. 			if (barrier(i, j, Arr, k)) { // Если ячейка преграда, делаем кол-во способов добраться до нее 0, чтобы дальнейшие ячейки не могли иметь путь через нее
  44. 				possible[i][j] = 0;
  45. 				continue;
  46. 			}
  47. 			if (start) {
  48. 				if (i == 0) {
  49. 					possible[i][j] = possible[i][j-1]; // Если ячейки из верхней строчки, то можем попасть в нее только с левой ячейки, получаем из нее коли-чество способов добраться
  50. 					continue;
  51. 				}
  52. 				if (j == 0) { // Если ячейка из левого столбика, то можем попасть в нее только сверху, получаем из нее коли-чество способов добраться
  53. 					possible[i][j] = possible[i-1][j];
  54. 					continue;
  55. 				}
  56. 				possible[i][j] = possible[i][j-1] + possible[i-1][j]; // В иных случаях прибавляем кол-во способов добраться из верхней ячейки и левой
  57. 			}
  58. 			else {
  59. 				start = true;
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	cout << possible[n-1][m-1]%1000000007; // Выводим остаток от деления на 1000000007
  65.  
  66. 	return 0;
  67. }
Success #stdin #stdout 0.01s 7260KB
comments (?)
stdin
copy 
1000 1000
1
2 2
stdout
copy 
723654130
https://ideone.com/3N8Nsk
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!