SHARE
TWEET

Untitled

a guest Oct 20th, 2019 159 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top