fork download
copy 
  1. #include<iostream>
  2.  
  3. using namespace std;
  4. int n, m, k, Q;
  5. bool check[1001][1001];
  6. long long dp[1001][1001];
  7. int xx[4] = { -1,1,2,2 };
  8. int yy[4] = { 2,2,1,-1 };
  9.  
  10. const long long mod = 1e9;
  11.  
  12. long long dynamic(int x, int y)
  13. {
  14. 	check[x][y] = true;
  15. 	for (int i = 0; i < 4; i++)
  16. 	{
  17. 		int a = x + xx[i], b = y + yy[i];
  18.  
  19. 		if (((a >= 1 && a <= n) && (b >= 1 && b <= m)) && check[a][b])
  20. 			dp[x][y] = ((dp[x][y] % mod) + (dp[a][b] % mod)) % mod;
  21. 		else if (((a >= 1 && a <= n) && (b >= 1 && b <= m)))
  22. 			dp[x][y] = ((dp[x][y] % mod) + (dynamic(a, b) % mod)) % mod;
  23. 	}
  24. 	return dp[x][y];
  25. }
  26. int main()
  27. {
  28. 	freopen("SOCACH.inp", "r", stdin);
  29. 	freopen("SOCACH.out", "w", stdout);
  30. 	cin >> n >> m >> k >> Q;
  31. 	for (int i = 0; i < k; i++)
  32. 	{
  33. 		int x, y;
  34. 		cin >> x >> y;
  35. 		check[x][y] = true;
  36. 	}
  37. 	check[n][m] = true;
  38. 	dp[n][m] = 1;
  39. 	for (int i = 0; i < Q; i++)
  40. 	{
  41. 		int x, y;
  42. 		cin >> x >> y;
  43. 		if (check[x][y])
  44. 			cout << dp[x][y] << endl;
  45. 		else
  46. 			cout << dynamic(x, y) << endl;
  47. 	}
  48. }
  49.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ruUSHh
language:
C++ (gcc 8.3)
created:
139 days 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!