Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned int ui;
  5.  
  6. int dr[] = {1, 0, -1, 0};
  7. int dc[] = {0, 1, 0, -1};
  8.  
  9. int main() {
  10. ios::sync_with_stdio(0);
  11. cin.tie(0); cout.tie(0);
  12.  
  13. int rows, cols;
  14. string word;
  15.  
  16. cin >> rows >> cols;
  17.  
  18. char keyboard[rows][cols];
  19. int dp[rows][cols];
  20. memset(keyboard, 0, sizeof(keyboard));
  21.  
  22. for (int r = 0; r < rows; r++) {
  23. for (int c = 0; c < cols; c++) {
  24. cin >> keyboard[r][c];
  25. dp[r][c] = -1;
  26. }
  27. }
  28. cin >> word;
  29. word += '*';
  30.  
  31. queue<tuple<int, int, int>> q;
  32. q.emplace(0, 0, 0);
  33. ui strokesUsed = 0;
  34. while (!q.empty()) {
  35. strokesUsed++;
  36. ui size = q.size();
  37. for (ui i = 0; i < size; i++) {
  38. tuple<int, int, int> c = q.front();
  39. q.pop();
  40. int x = get<0>(c);
  41. int y = get<1>(c);
  42. int index = get<2>(c);
  43. if (dp[x][y] >= index)
  44. continue;
  45. dp[x][y] = index;
  46. if (keyboard[x][y] == word[index]) {
  47. index++;
  48. if (index == (int)word.size()) {
  49. cout << strokesUsed;
  50. return 0;
  51. }
  52. q.emplace(x, y, index);
  53. // cout << word.substr(0, index) << ' ' << x << ' ' << y << ' ' << index << ' ' << strokesUsed << " \n";
  54. continue;
  55. }
  56. for (int j = 0; j < 4; j++) {
  57. int nx = x;
  58. int ny = y;
  59. while (nx >= 0 && ny >= 0 && nx < rows && ny <= cols && keyboard[nx][ny] == keyboard[x][y]) {
  60. nx += dr[j];
  61. ny += dc[j];
  62. }
  63. if (nx < 0 || ny < 0 || nx >= rows || ny >= cols)
  64. continue;
  65. q.emplace(nx, ny, index);
  66. }
  67. }
  68. }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement