算法题: 找到它

标题: 找到它

题描述

找到它是一个小游戏,你需要在一个矩阵中找到给定的单词。假定给定的单词是HELLOWORLD,在矩阵中只需要找到H->E->L->L->O->W->O->R->L->D连成的单词,就算通过。
注意区分英文字母大小写, 并且只能上下左右行走，不可以回头

输入描述

输入第一行包含两个整数rows,cols(0 < rows,cols < 21)分别表示矩阵的行数rows和列数cols.
第二行是一个长度不超过100的单词，在给定的矩阵中，整个单词只会出现一次，从第三行到第rows + 2行是包含大小写英文字母的长度为cols的字符矩阵

输出描述

如果能在矩阵中找到对应的单词, 输入所在对应单词第一个字母所在的行和列，否则输出NO

测试示例

输入:

5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC

输出

3 2

解题思路

1. 首先想到使用回溯法
2. 遍历矩阵元素,找到单词第一个字母所在位置, 标记该位置被占用, 并从该位置开始检验是否能找到对应的单词,找到则返回行和列的索引
3. 检验时, 依次检验当前位置的左上右下等位置的flag值,flag未标记时判断该位置的字母是否和目标单词当前索引的下一个位置的字母相等, 相等则标记该位置的flag为占用状态并以该位置进行下一轮递归检验, 直到单词下一个索引的字符变为’\0’，检验不通过时,将对应位置的flag回溯为false

示例代码

#include <vector>
#include <iostream>


struct Matrix {
    Matrix(int rows, int cols): m_rows(rows), m_flags(rows) {
        for(auto& row: m_rows) {
            row.resize(cols);
        }

        for(auto& row: m_flags) {
            row.resize(cols);
        }
    }

    bool find(const char *target, int& row, int& col) {


        for (auto i = 0; i < m_rows.size(); ++i) {
            for (auto j = 0; j < m_rows[i].size(); ++j) {
                if (m_rows[i][j] == *target) {
                    m_flags[i][j] = true;
                    if (check(target, i, j)) {
                        row = i;
                        col = j;
                        return true;
                    }
                    m_flags[i][j] = false;
                }
            }
        }


        return false;
    }

    bool check(const char *target, int row, int col) {

        if (target and *target != '\0' and target[1] != '\0') {

            if (0 < row and not m_flags[row - 1][col] and m_rows[row - 1][col] == target[1]) {
                m_flags[row - 1][col] = true;
                if (check(target + 1, row - 1, col)) {
                    return true;
                }
                m_flags[row - 1][col] = false;
            }

            if (0 < col and not m_flags[row][col - 1] and m_rows[row][col - 1] == target[1]) {
                m_flags[row][col - 1] = true;
                if (check(target + 1, row, col - 1)) {
                    return true;
                }
                m_flags[row][col - 1] = false;
            }

            if (row < m_rows.size() - 1 and not m_flags[row + 1][col] and m_rows[row + 1][col] == target[1]) {
                m_flags[row + 1][col] = true;
                if (check(target + 1, row + 1, col)) {
                    return true;
                }
                m_flags[row + 1][col] = false;
            }

            if (col < m_rows[row].size() - 1 and not m_flags[row][col + 1] and m_rows[row][col + 1] == target[1]) {
                m_flags[row ][col + 1] = true;
                if (check(target + 1, row, col + 1)) {
                    return true;
                }
                m_flags[row][col + 1] = false;
            }

            return false;

        }
        return true;
    }

    template<typename InputStream>
    InputStream& input(InputStream& in) {

        for(auto i = 0; i < m_rows.size(); ++i) {
            std::string line;
            in >> line;
            m_rows[i].assign(line.begin(), line.end());
        }

        return in;
    }


private:
    std::vector<std::vector<char>> m_rows;
    std::vector<std::vector<bool>> m_flags;
};

template<typename InputStream>
InputStream& operator>>(InputStream& in, Matrix& m) {
    return m.input(in);
}



int main() {

    int row, col;
    std::string target;

    std::cin >> row >> col >> target;

    Matrix m(row, col);

    std::cin >> m;


    if (m.find(target.c_str(), row, col)) {
        std::cout << row + 1 << ' ' << col + 1 << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }

    return 0;
}