ognjen_neskovic

Tastatura

Apr 8th, 2021
459
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <queue>
  6. #include <map>
  7. using namespace std;
  8. #define ll long long
  9.  
  10. struct cell
  11. {
  12.     int index, value;
  13. };
  14.  
  15. int char_to_int(char c)
  16. {
  17.     if (c == '*')
  18.         return 26;
  19.     else
  20.         return c - 'A';
  21. }
  22. vector<int> str_to_vector_int(string s)
  23. {
  24.     vector<int> v(s.size());
  25.     for (size_t i = 0; i < s.size(); i++)
  26.         v[i] = char_to_int(s[i]);
  27.     return v;
  28. }
  29.  
  30. bool is_valid_cell(int row, int col, int row_count, int col_count)
  31. {
  32.     if (row < 0 || col < 0 || row >= row_count || col >= col_count)
  33.     {
  34.         return false;
  35.     }
  36.     return true;
  37. }
  38.  
  39. vector<cell> get_neighbors(int row, int col, const vector<vector<int>>& keyboard)
  40. {
  41.     vector<int> drow = { 0,0,1,-1 };
  42.     vector<int> dcol = { 1,-1,0,0 };
  43.     vector<cell> neighbors;
  44.  
  45.     int current_row = row;
  46.     int current_col = col;
  47.  
  48.     int col_count = keyboard[0].size();
  49.     for (int i = 0; i < drow.size(); i++)
  50.     {
  51.         int new_row = current_row + drow[i];
  52.         int new_col = current_col + dcol[i];
  53.         while (is_valid_cell(new_row, new_col, keyboard.size(), keyboard[0].size()) && keyboard[new_row][new_col] == keyboard[current_row][current_col])
  54.         {
  55.             current_row = new_row;
  56.             current_col = new_col;
  57.             new_row += drow[i];
  58.             new_col += dcol[i];
  59.         }
  60.         if (is_valid_cell(new_row, new_col, keyboard.size(), keyboard[0].size()))
  61.         {
  62.             int index = new_row * col_count + new_col;
  63.             neighbors.push_back({ index, keyboard[new_row][new_col] });
  64.         }
  65.         else
  66.         {
  67.             int index = current_row * col_count + current_col;
  68.             neighbors.push_back({index,keyboard[current_row][current_col]});
  69.         }
  70.         current_row = row;
  71.         current_col = col;
  72.     }
  73.     return neighbors;
  74. }
  75.  
  76. vector<ll> shortest_paths(cell source_node, const vector<vector<cell>>& graph)
  77. {
  78.     queue<pair<cell, ll>> bfs_queue;
  79.     vector<ll> computed_path(graph.size(), -1);
  80.     bfs_queue.push({ source_node, 0 });
  81.     computed_path[source_node.index] = 0;
  82.     while (!bfs_queue.empty())
  83.     {
  84.         auto current_cell = bfs_queue.front().first;
  85.         ll dist = bfs_queue.front().second;
  86.         bfs_queue.pop();
  87.  
  88.         for (auto neighbor : graph[current_cell.index])
  89.         {
  90.             if (computed_path[neighbor.index] == -1)
  91.             {
  92.                 bfs_queue.push({ neighbor, dist + 1 });
  93.                 computed_path[neighbor.index] = dist + 1;
  94.             }
  95.         }
  96.     }
  97.     return computed_path;
  98. }
  99.  
  100. void debug_print(const vector<vector<int>>& dp, int pos)
  101. {
  102.     int n = 5, m = 5;
  103.     for (int i = 0; i < n; i++)
  104.     {
  105.         for (int j = 0; j < m; j++)
  106.         {
  107.             int index = i * m + j;
  108.             cout << dp[index][pos] << " ";
  109.         }
  110.         cout << "\n";
  111.     }
  112. }
  113.  
  114. ll solve(const vector<int>& str_to_find, const vector<vector<cell>>& graph, const vector<vector<int>>& k)
  115. {
  116.     vector<vector<ll>> shortest_path_from_to(graph.size(), vector<ll>());
  117.     for (int i = 0; i < graph.size(); i++)
  118.         shortest_path_from_to[i] = shortest_paths({ i,-1 }, graph);
  119.  
  120.     vector<vector<int>> indices_with_chr (27, vector<int>());
  121.     vector<int> keyboard(k.size() * k[0].size());
  122.     for (int row = 0; row < k.size(); row++)
  123.     {
  124.         for (int col = 0; col < k[0].size(); col++)
  125.         {
  126.             int index = row * k[0].size() + col;
  127.             keyboard[index] = k[row][col];
  128.             indices_with_chr[k[row][col]].push_back(index);
  129.         }
  130.     }
  131.  
  132.     vector<vector<ll>> dp(graph.size(), vector<ll>(str_to_find.size(), -1));
  133.    
  134.     for (int i = 0; i < dp.size(); i++)
  135.     {
  136.         dp[i][0] = shortest_path_from_to[0][i];
  137.     }
  138.     //debug_print(dp, 0);
  139.    
  140.     for (int pos_in_str = 1; pos_in_str < str_to_find.size(); pos_in_str++)
  141.     {
  142.         for (int i = 0; i < graph.size(); i++)
  143.         {
  144.             if (dp[i][pos_in_str-1] == -1)
  145.             {
  146.                 continue;
  147.             }
  148.             if (keyboard[i] == str_to_find[pos_in_str])
  149.             {
  150.                 if (dp[i][pos_in_str-1] == -1)
  151.                     dp[i][pos_in_str] = -1;
  152.                 else
  153.                     dp[i][pos_in_str] = dp[i][pos_in_str - 1];
  154.             }
  155.             else
  156.             {
  157.                 ll min_over_all_neighbors = LLONG_MAX;
  158.                 for (int neighbor: indices_with_chr[str_to_find[pos_in_str]])
  159.                 {
  160.                     if (dp[neighbor][pos_in_str - 1] > -1)
  161.                     {
  162.                         min_over_all_neighbors = min(min_over_all_neighbors, dp[neighbor][pos_in_str - 1] + shortest_path_from_to[neighbor][i]);
  163.                     }
  164.                 }
  165.                 if (min_over_all_neighbors == LLONG_MAX)
  166.                     dp[i][pos_in_str] = -1;
  167.                 else
  168.                     dp[i][pos_in_str] = min_over_all_neighbors;
  169.             }
  170.         }
  171.         //debug_print(dp, pos_in_str);
  172.     }
  173.  
  174.     ll solution = INT_MAX;
  175.     for (int i = 0; i < graph.size(); i++)
  176.     {
  177.         if (keyboard[i] == 26 && dp[i].back() > -1)
  178.         {
  179.             solution = min(solution, dp[i].back());
  180.         }
  181.     }
  182.     return solution;
  183. }
  184.  
  185. int main()
  186. {
  187.     ios::sync_with_stdio(false);
  188.     cin.tie(0);
  189.  
  190.     int row_count, col_count;
  191.     cin >> row_count >> col_count;
  192.     vector<vector<int>> keyboard(row_count, vector<int>(col_count));
  193.     for (int row = 0; row < row_count; row++)
  194.     {
  195.         string s; cin >> s;
  196.         keyboard[row] = str_to_vector_int(s);
  197.     }
  198.  
  199.     int max_value = 26;
  200.     vector<vector<cell>> graph(row_count*col_count, vector<cell>());
  201.     for (int row = 0; row < row_count; row++)
  202.     {
  203.         for (int col = 0; col < col_count; col++)
  204.         {
  205.             int index = row * col_count + col;
  206.             auto neighbors = get_neighbors(row, col, keyboard);
  207.             for (auto n : neighbors)
  208.             {
  209.                 graph[index].push_back(n);
  210.             }
  211.         }
  212.     }
  213.  
  214.     string str_to_type; cin >> str_to_type;
  215.     auto vec_to_type = str_to_vector_int("A"+str_to_type+"*");
  216.     cout << solve(vec_to_type, graph, keyboard) + str_to_type.size()+1;
  217.     return 0;
  218. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×