Как найти последовательность букв через графы?

Question

[impelix]

Задача:
На вход подается 2 числа n и m, и потом n строк по m символов, потом координаты x и y, задача найти искомое слово которое подается далее в строку, от каждой буквы можно переходить в соседние(не по диагонали), задача найти минимальный путь, соединив все искомые буквы. Мой код ниже. Пытался перенести на графы и найти по алгоритму Флойда — Уоршелла. Первый тест проходит, а второй нет.

код

#include <iostream>
#include <vector>
#include <algorithm>
/*2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
*/

struct tchk {
    int x, y, amount;
    bool operator<(const int &r){
        return this->amount < r;
    }
};

int n, m;
std::string target;
std::vector<std::vector<char>> mas(n);

int find(std::vector<std::vector<int>>& g){
    int sum = 0;
    tchk mn = { 0, 0, INT_MAX };
    for (auto k : target) {
        int x = mn.x;
        int y = mn.y;
        g[x][y] = 0;
        for (int k = 0; k < n * m; ++k)
            for (int i = 0; i < n * m; ++i)
                for (int j = 0; j < n * m; ++j)
                    if (g[i][j] > g[i][k] + g[k][j])
                        g[i][j] = g[i][k] + g[k][j];
        int i, j;
        mn.amount = INT16_MAX;
        std::cout << "i want find " << k << '\n';
        for (i = 0; i < n; i++)
            for (j = 0; j < m; j++) {
                int temp = g[y][i * m + j];
                mn = mn;
                if (mas[i][j] == k)
                    if (mn.amount > temp) {
                        mn.x = x * m + y;
                        mn.y = i * m + j;
                        mn.amount = temp;
                    }

            }
        sum += mn.amount;
        std::cout << sum << '\n';
        g.resize(n * m, std::vector<int>(n * m, INT_MAX));
        for (int i = 0; i < n * m; i++)
            for (int j = 0; j < m * n; j++) {
                if (((i - j == 1 or j - i == 1) and (j % m != 0 and i % m != 0) and (i != 0 or j != 0)) or i - j == m or j - i == m)
                    g[i][j] = g[j][i] = 1;
                g[1][0] = 1;
                g[0][1] = 1;
            }
        for (int i = 0; i < n * m; ++i)
            g[i][i] = 0;
        //std::cout << k;
    }
    return sum;
}
int main() {
    int x, y;
    std::cin >> n >> m >> x >> y;
    --x;
    --y;
    std::vector<std::vector<int>> g(n * m, std::vector<int>(n * m, INT16_MAX));
    g[x][y] = 0;
    for (int i = 0; i < n; i++) {
        std::string h;
        std::cin >> h;
        std::vector<char>mm;
        for (auto temp : h) {
            mm.push_back(temp);
        }
        mas.push_back(mm);
    }
    /*for (auto k : mas) {
        for (auto j : k)
              std::cout << j << ' ';
        std::cout << '\n';
    }*/
    //std::string target;
    std::cin >> target;

    for (int i = 0; i < n * m; i++)
        for (int j = 0; j < m * n; j++) {
            if (((i - j == 1 or j - i == 1) and (j % m != 0 and i % m != 0) and (i != 0 or j != 0)) or i - j == m or j - i == m)
                g[i][j] = g[j][i] = 1;
            g[1][0] = 1;
            g[0][1] = 1;
        }
   /* for (auto k : g) {
        for (auto j : k)
            std::cout << j << ' ';
        std::cout << '\n';
    }*/
    for (int i = 0; i < n * m; ++i)
        g[i][i] = 0;

    //int temp;
    //std::cin >> temp;
    std::cout << find(g);
    return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
/*2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
*/

struct tchk {
    int x, y, amount;
    bool operator<(const int &r){
        return this->amount < r;
    }
};

int n, m;
std::string target;
std::vector<std::vector<char>> mas(n);

int find(std::vector<std::vector<int>>& g){
    int sum = 0;
    tchk mn = { 0, 0, INT_MAX };
    for (auto k : target) {
        int x = mn.x;
        int y = mn.y;
        g[x][y] = 0;
        for (int k = 0; k < n * m; ++k)
            for (int i = 0; i < n * m; ++i)
                for (int j = 0; j < n * m; ++j)
                    if (g[i][j] > g[i][k] + g[k][j])
                        g[i][j] = g[i][k] + g[k][j];
        int i, j;
        mn.amount = INT16_MAX;
        std::cout << "i want find " << k << '\n';
        for (i = 0; i < n; i++)
            for (j = 0; j < m; j++) {
                int temp = g[y][i * m + j];
                mn = mn;
                if (mas[i][j] == k)
                    if (mn.amount > temp) {
                        mn.x = x * m + y;
                        mn.y = i * m + j;
                        mn.amount = temp;
                    }

            }
        sum += mn.amount;
        std::cout << sum << '\n';
        g.resize(n * m, std::vector<int>(n * m, INT_MAX));
        for (int i = 0; i < n * m; i++)
            for (int j = 0; j < m * n; j++) {
                if (((i - j == 1 or j - i == 1) and (j % m != 0 and i % m != 0) and (i != 0 or j != 0)) or i - j == m or j - i == m)
                    g[i][j] = g[j][i] = 1;
                g[1][0] = 1;
                g[0][1] = 1;
            }
        for (int i = 0; i < n * m; ++i)
            g[i][i] = 0;
        //std::cout << k;
    }
    return sum;
}
int main() {
    int x, y;
    std::cin >> n >> m >> x >> y;
    --x;
    --y;
    std::vector<std::vector<int>> g(n * m, std::vector<int>(n * m, INT16_MAX));
    g[x][y] = 0;
    for (int i = 0; i < n; i++) {
        std::string h;
        std::cin >> h;
        std::vector<char>mm;
        for (auto temp : h) {
            mm.push_back(temp);
        }
        mas.push_back(mm);
    }
    /*for (auto k : mas) {
        for (auto j : k)
              std::cout << j << ' ';
        std::cout << '\n';
    }*/
    //std::string target;
    std::cin >> target;

    for (int i = 0; i < n * m; i++)
        for (int j = 0; j < m * n; j++) {
            if (((i - j == 1 or j - i == 1) and (j % m != 0 and i % m != 0) and (i != 0 or j != 0)) or i - j == m or j - i == m)
                g[i][j] = g[j][i] = 1;
            g[1][0] = 1;
            g[0][1] = 1;
        }
   /* for (auto k : g) {
        for (auto j : k)
            std::cout << j << ' ';
        std::cout << '\n';
    }*/
    for (int i = 0; i < n * m; ++i)
        g[i][i] = 0;

    //int temp;
    //std::cin >> temp;
    std::cout << find(g);
    return 0;
}

тест 1

2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
ответ 17

тест 2

7 7
4 4
abcdefg
xyzabch
wnopqdi
vmvwrej
ulutsfk
tkjihgl
srqponm
squirrel
ответ 17

Comments

[Wataru]

Т. е, начав с заданной координаты, надо пройти минимальный путь, что бы посетить какие-то клетки с буквами из зданного слова по порядку? А что делать со словом "aaa"? Надо ли три раза наступить на клетку с a, или можно ее один раз посетить? Какие ограничения?

Answer 1

[Wataru]

Похоже, эта задача решается обходом в ширину на модифицированном графе. Пусть l длина искомой строки.

Тогда постройте граф на n*m*l вершин. Каждая вершина соответствует тройке (x, y, k) и означает, что мы как-то походили по полю и оказались в координате (x, y), при этом набрав первые k символов искомой строки. Переходы в графе тут такие: от каждой вершины можно пойти в 4 соседние по координатам, а количество символов увеличивается на 1, если в следующей вершине читается следующая буква строки. Т.е. переходы вида (x, y, k) -> (x+1, y, k + (s[k] == grid[x+1][y] ? 1 : 0)); (x, y, k) -> (x, y+1, k + (s[k] == grid[x][y+1] ? 1 : 0)) и еще 2 на минус (если x,y не у стенки поля, естественно - некоторые переходы могут отсутствовать).

Ищите кратчайшее расстояние из вершины (x0, y0, s[0] == grid[x0][y0] ? 1 : 0) в любую вершину с третим индексом равным l (т.е. любое место, где вы прочтете всю искомую строку). Поскольку в графе все ребра длины 1, можно запускать bfs. Граф строить и охранить не надо, можно эти 4 перехода вычислять неявно. Кладите в очередь тройки чисел, вынимайте их оттуда и вычисляйте до 4 соседних троек, которые гужно тоже сложить в очередь обхода в ширину. Удобно завести 2 костантных массива на 4 элемента, которые будут хранить приращения по x и по y в каждую их четрех сторон. Тогда не будет много дублируемого кода.

Еще понадобится, таки, массив на n*m*l для хранения расстояния, или хотя бы пометок о том, что вершина уже в очередь была положена.

Comments

[Alexandroppolus]

в искомом слове надо предварительно убрать все повторы символов на соседних позициях ("aaabbcc" превращается в "abc"), иначе понадобились бы ещё переходы (x, y, k) -> (x, y, k+1)

[Wataru]

Alexandroppolus, это зависит от условия. Может, для повтора надо сходить в соседнюю клетку и обратно. Тогда никакие повторы обрабатывать не надо. Вообще, второй тест из вопроса это покажет, но мне лень отсчитывать там шаги. Но если все символы повтора съедаются за один шаг, то еще можно переходы делать не на +1 в третьем индексе, а на + сколько там одинаковых символов из матрицы в этой позиции встречается.