fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <array>
  6. using namespace std;
  7. typedef long long ll;
  8. #define SZ(a) (int)(a).size()
  9.  
  10. const int mod = 1000000007;
  11.  
  12. int main() {
  13. 	cin.sync_with_stdio(false);
  14. 	int n, m, k;
  15. 	cin >> n >> m >> k;
  16. 	vector<string> a(n);
  17. 	int sx, sy;
  18. 	for (int i = 0; i < n; i++) {
  19. 		cin >> a[i];
  20. 		auto j = a[i].find('R');
  21. 		if (j != string::npos) {
  22. 			sx = i;
  23. 			sy = j;
  24. 		}
  25. 	}
  26. 	array<vector<vector<int>>,2> dp;
  27. 	for (int l = 0; l < 2; l++) {
  28. 		dp[l].assign(n, vector<int>(m, 0));
  29. 	}
  30. 	dp[0][sx][sy] = 1;
  31. 	for (int l = 1; l <= k; l++) {
  32. 		auto cur = l & 1;
  33. 		auto prv = cur ^ 1;
  34. 		for (int i = 0; i < n; i++) {
  35. 			for (int j = 0; j < m; j++) {
  36. 				dp[cur][i][j] = 0;
  37. 				if (a[i][j] != '#') {
  38. 					if (i > 0) {
  39. 						dp[cur][i][j] += dp[prv][i-1][j];
  40. 						dp[cur][i][j] %= mod;
  41. 					}
  42. 					if (i < n-1) {
  43. 						dp[cur][i][j] += dp[prv][i+1][j];
  44. 						dp[cur][i][j] %= mod;
  45. 					}
  46. 					if (j > 0) {
  47. 						dp[cur][i][j] += dp[prv][i][j-1];
  48. 						dp[cur][i][j] %= mod;
  49. 					}
  50. 					if (j < m-1) {
  51. 						dp[cur][i][j] += dp[prv][i][j+1];
  52. 						dp[cur][i][j] %= mod;
  53. 					}
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. 	auto cur = k & 1;
  59. 	for (int i = 0; i < n; i++) {
  60. 		for (int j = 0; j < m; j++) {
  61. 			printf("%d%c", dp[cur][i][j], " \n"[j == m-1]);
  62. 		}
  63. 	}
  64. 	return 0;
  65. }
  66.  
Runtime error #stdin #stdout #stderr 0s 15584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/NmnR8r
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!