Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned int ui;
- int dr[] = {1, 0, -1, 0};
- int dc[] = {0, 1, 0, -1};
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int rows, cols;
- string word;
- cin >> rows >> cols;
- char keyboard[rows][cols];
- int dp[rows][cols];
- memset(keyboard, 0, sizeof(keyboard));
- for (int r = 0; r < rows; r++) {
- for (int c = 0; c < cols; c++) {
- cin >> keyboard[r][c];
- dp[r][c] = -1;
- }
- }
- cin >> word;
- word += '*';
- queue<tuple<int, int, int>> q;
- q.emplace(0, 0, 0);
- ui strokesUsed = 0;
- while (!q.empty()) {
- strokesUsed++;
- ui size = q.size();
- for (ui i = 0; i < size; i++) {
- tuple<int, int, int> c = q.front();
- q.pop();
- int x = get<0>(c);
- int y = get<1>(c);
- int index = get<2>(c);
- if (dp[x][y] >= index)
- continue;
- dp[x][y] = index;
- if (keyboard[x][y] == word[index]) {
- index++;
- if (index == (int)word.size()) {
- cout << strokesUsed;
- return 0;
- }
- q.emplace(x, y, index);
- // cout << word.substr(0, index) << ' ' << x << ' ' << y << ' ' << index << ' ' << strokesUsed << " \n";
- continue;
- }
- for (int j = 0; j < 4; j++) {
- int nx = x;
- int ny = y;
- while (nx >= 0 && ny >= 0 && nx < rows && ny <= cols && keyboard[nx][ny] == keyboard[x][y]) {
- nx += dr[j];
- ny += dc[j];
- }
- if (nx < 0 || ny < 0 || nx >= rows || ny >= cols)
- continue;
- q.emplace(nx, ny, index);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement