找单词

题目描述

给一个字符串和一个二维字符数组, 如果该字符串存在于该数组中, 则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串, 如果找不到返回字符串 N.

• 需要按照字符串的字符组成顺序搜索, 且搜索到的位置必须是相邻单元格, 其中 相邻单元格 是指那些水平相邻或垂直相邻的单元格
• 同一个单元格内的字母不允许被重复使用
• 假定在数组中最多只存在一个可能的匹配

输入描述

• 第1行为一个数字N指示二维数组在后续输入所占的行数
• 第2行到第N+1行输入为一个二维大写字符数组, 每行字符用半角, 分割
• 第N+2行为待查找的字符串, 由大写字符组成
• 二维数组的大小为N*N, 0<N<=100
• 单词长度K, 0<K<1000

输出描述

出一个位置下标字符串, 拼接格式为:

第1个字符行下标 + , + 第1个字符列下标 + , + 第2个字符行下标 + , + 第2个字符列下标… + 第N个字符列下标

示例1

输入:

4
A,C,C,F
C,D,E,D
B,E,S,S
F,E,C,A
ACCESS

输出:

0,0,0,1,0,2,1,2,2,2,2,3

题解

Python

def main():
    # 读取字母的行数
    rows = int(input())
    # 字母表, N * N 的二维数组
    table = []
    for _i in range(rows):
        # 读取当前行的所有字母
        table.append(list(input().split(",")))
        assert len(table[-1]) == rows
    # 读取输入的单词
    word = input()

    # 用于标记已经访问过的字符, N * N
    visited = [[False] * rows for _row in range(rows)]

    # 定义查找的四个方向
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    # 使用DFS搜索所有可能的位置
    def dfs(row: int, column: int, index_in_word: int, path):
        # 结束查找
        # 1. 检查坐标的边界, 如果不在 table 内
        # 2. 或者已经访问过了
        # 3. 或者单词中的字母与在表格中的不一致
        if row < 0 or row >= rows or column < 0 or column >= rows or \
                visited[row][column] or \
                word[index_in_word] != table[row][column]:
            return False
        # 将当前路径添加到 path 中
        path.append((row, column))
        # 并标记该节点已经访问过
        visited[row][column] = True
        # 如果单词中的所有字母都被找到了, 就返回
        if index_in_word + 1 == len(word):
            return True

        # 遍历所有可能的方向, 进行深入查找
        for direction in directions:
            row2 = row + direction[0]
            column2 = column + direction[1]
            # 去找单词中的下一个字母
            found = dfs(row2, column2, index_in_word + 1, path)
            # 如果在该方向找到了字符串, 就直接返回
            if found:
                return True
        # 没有找到, 当前前位置从经过的路径中移除
        path.pop()
        # 并将该坐标从被访问记录中移除
        visited[row][column] = False
        return False

    def find_string():
        # 用于存储访问路径
        path= []
        # 遍历所有的单元格
        for row in range(rows):
            for column in range(rows):
                # 如果当前单元格的字符等于单词的第一个字母
                if table[row][column] == word[0]:
                    # 使用DFS查找字符串
                    found = dfs(row, column, 0, path)
                    if found:
                        # 找到了, 就返回结果
                        positions = []
                        for row, column in path:
                            positions.append(str(row))
                            positions.append(str(column))
                        result = ",".join(positions)
                        return result

        # 没有找到合适的
        return "N"

    result = find_string()
    # 打印最后的结果
    print(result)


if __name__ == "__main__":
    main()

C++

#include <cassert>

#include <array>
#include <iostream>
#include <vector>

bool dfs(const std::vector<std::vector<char>>& table,
         std::vector<std::vector<bool>>& visited,
         std::vector<std::pair<int, int>>& path,
         const std::string& word, int word_index,
         int row, int column) {
  const int rows = table.size();
  const int columns = rows;
  // 结束查找:
  // 1. 检查坐标的边界, 如果不在 table 内
  // 2. 或者已经访问过了
  // 3. 或者单词中的字母与在表格中的不一致
  if (row < 0 || row >= rows || column < 0 || column >= columns || 
      visited[row][column] || word[word_index] != table[row][column]) {
    return false;
  }

  // 将当前路径添加到 path 中
  path.emplace_back(row, column);
  // 并标记该节点已经访问过
  visited[row][column] = true;
  // 如果单词中的所有字母都被找到了, 就返回
  if (word_index + 1 == word.size()) {
    return true;
  }
    
  // 定义查找的四个方向
  const std::array<std::array<int, 2>, 4> directions = {
      std::array<int, 2>{1, 0}, {-1, 0}, {0, 1}, {0, -1}
  };

  // 遍历所有可能的方向, 进行深入查找
  for (const std::array<int, 2> dir : directions) {
    const int row1 = row + dir[0];
    const int column1 = column + dir[1];
    // 去找单词中的下一个字母
    const bool found = dfs(table, visited, path, word, word_index + 1, row1, column1);
    // 如果在该方向找到了字符串, 就直接返回
    if (found) {
      return true;
    }
  }

  // 没有找到, 当前前位置从经过的路径中移除
  path.pop_back();
  // 并将该坐标从被访问记录中移除
  visited[row][column] = false;
  return false;
}

void solution() {
  // 读取输入
  int rows = 0;
  std::cin >> rows;
  // 换行符
  std::string line;
  std::cin >> line;
  // 读取所有字符表
  std::vector<std::vector<char>> table;
  for (int row = 0; row < rows; ++row) {
    std::vector<char> row_chars(rows);
    for (char& c : row_chars) {
      std::cin >> c;
    }
    // 换行符
    std::cin >> line;
    table.emplace_back(row_chars);
  }
  // 读取单词
  std::string word;
  std::cin >> word;

  // 用于标记已经访问过的字符, N * N
  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(rows));
  // 用于存储访问路径
  std::vector<std::pair<int, int>> path;

  const int columns = rows;
  // 遍历所有字符
  for (int row = 0; row < rows; ++row) {
    for (int column = 0; column < columns; ++column) {
      // 如果当前单元格的字符等于单词的第一个字母
      if (word[0] == table[row][column]) {
        // 使用DFS查找字符串
        const bool found = dfs(table, visited, path, word, 0, row, column);
        if (found) {
          // 找到了, 就返回结果
          for (const auto& pair : path) {
            std::cout << pair.first << "," << pair.second << std::endl;
          }
          return;
        }
      }
    }
  }

  std::cout << "N" << std::endl;
}

int main() {
  // FIXME(Shaohua): Result invalid
  solution();
  return 0;
}