Guest User

Untitled

a guest
Oct 20th, 2019
231
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstring>
  5. using namespace std;
  6.  
  7. const int MAX = 100;
  8. const int MAX_LENGTH = 80;
  9.  
  10. typedef struct
  11. {
  12. int y, x;
  13. }Dir;
  14.  
  15. Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
  16.  
  17. int N, M, K;
  18. int result;
  19. string target;
  20. string board[MAX];
  21. int cache[MAX][MAX][MAX_LENGTH];
  22.  
  23. int func(int y, int x, int idx)
  24. {
  25. int &result = cache[y][x][idx];
  26.  
  27. if (result != -1)
  28. {
  29. return result;
  30. }
  31.  
  32. if (idx == target.length())
  33. {
  34. return 1;
  35. }
  36.  
  37. result = 0;
  38.  
  39. for (int k = 0; k < 4; k++)
  40. {
  41. int tempY = y;
  42. int tempX = x;
  43.  
  44. for (int i = 0; i < K; i++)
  45. {
  46. int nextY = tempY + moveDir[k].y;
  47. int nextX = tempX + moveDir[k].x;
  48.  
  49. if (nextY < 0 || nextY >= N || nextX < 0 || nextX > M)
  50. {
  51. break;
  52. }
  53.  
  54. if (board[nextY][nextX] == target[idx])
  55. {
  56. result += func(nextY, nextX, idx + 1);
  57. }
  58.  
  59. tempY = nextY;
  60. tempX = nextX;
  61. }
  62. }
  63.  
  64. return result;
  65. }
  66.  
  67. int main(void)
  68. {
  69. ios_base::sync_with_stdio(0);
  70. cin.tie(0);
  71. cin >> N >> M >> K;
  72.  
  73. for (int i = 0; i < N; i++)
  74. {
  75. cin >> board[i];
  76. }
  77.  
  78. cin >> target;
  79.  
  80. vector<pair<int, int>> start;
  81.  
  82. for (int i = 0; i < N; i++)
  83. {
  84. for (int j = 0; j < M; j++)
  85. {
  86. if (board[i][j] == target[0])
  87. {
  88. start.push_back({ i, j });
  89. }
  90. }
  91. }
  92.  
  93. memset(cache, -1, sizeof(cache));
  94.  
  95. for (int i = 0; i < start.size(); i++)
  96. {
  97. int y = start[i].first;
  98. int x = start[i].second;
  99.  
  100. result += func(y, x, 1);
  101. }
  102.  
  103. cout << result << "\n";
  104.  
  105. return 0;
  106. }
RAW Paste Data