最新华为OD机试考点合集：华为OD机试2024年真题题库（E卷+D卷+C卷）_华为od机试题库-CSDN博客
题目描述
给一个字符串和一个 二维字符数组，如果该字符串存在于该数组中，则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串，如果找不到返回字符串“N”
1.需要按照字符串的字符组成 顺序搜索，且搜索到的位置必须是相邻单元格，其中"相邻单元格"是指那些水平相邻或垂直相邻的单元格。
2.同一个单元格内的字母不允许被重复使用。
3.假定在数组中最多只存在一个可能的匹配。
输入描述
第1行为一个数字N指示二维数组在后续输入所占的行数。
第2行到第N+1行输入为一个二维大写字符数组，每行字符用半角,分割。
第N+2行为待查找的字符串，由大写字符组成。
维数组的大小为N*N，0<N<=100.
单词长度K，0<K<1000。
输出描述
输出一个位置下标字符串，拼接格式为:第1个字符行下标+","+第1个字符列下标+”,”+第2个字符行下标+""+第2个字符列下标.….-+""+第N个字符行下标+””+第N个字符列下标。示例1
输入
4
AC.CF
C,D,E,D
B,E,S,S
F,E,C,A
ACCESS输出
0.00 1.0.2.12.2.2.2.3
说明
ACCESS分别对应二维数组的[0,0][0,1][0,2][1,2][2,2][2,3]下标位置。
解题思路：
该题要求在一个二维字符数组中查找给定的字符串，并输出字符串中每个字符的坐标路径。字符之间的相邻性要求水平或垂直相邻，且每个字符只能使用一次。下面是具体的解题思路：
1. 问题分解
- 二维数组表示问题：给定的二维数组由大写字符组成，我们需要在其中找到目标字符串。如果目标字符串的字符序列在二维数组中按照相邻性规则存在，我们需要输出其字符所在单元格的坐标路径。
- 相邻单元格的定义：水平或垂直相邻，意味着从当前字符可以向上、下、左、右四个方向移动到下一个字符。
- 回溯问题：由于同一个单元格的字符只能使用一次，这类问题典型地可以使用深度优先搜索 (DFS) 与回溯算法来实现。
2. 深度优先搜索 (DFS)
- DFS的目标：DFS 的任务是找到目标字符串的每个字符，保证每个字符与前一个字符相邻。
- 递归搜索：从二维数组的每一个位置开始，依次查找字符串的每个字符。如果当前字符匹配，就递归查找它的相邻单元格中下一个字符。
- 回溯机制：每次递归查找字符时，需要标记当前单元格已访问过。如果后续搜索失败（即无法找到完整的字符串），需要“回溯”，即取消该单元格的访问标记，并继续探索其它路径。
3. 边界条件
- 越界判断：在进行搜索时，需要确保每次移动后的坐标在二维数组的有效范围内。
- 字符匹配：只有当当前单元格的字符与目标字符串当前索引的字符匹配时，才能继续搜索。
- 访问标记：每个单元格只能访问一次，因此需要用一个二维布尔数组 visited 来标记已经访问过的单元格，以防止重复使用同一个字符。
c++解法：
#include <iostream>
#include <vector>
#include <string>using namespace std;// 定义方向向量，上下左右
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 深度优先搜索 (DFS) 函数
bool dfs(const vector<vector<char>>& board, const string& word, int index, int x, int y, vector<vector<bool>>& visited, vector<pair<int, int>>& path) {// 如果匹配到目标字符串的最后一个字符，返回 trueif (index == word.size()) return true;int n = board.size();// 检查边界条件和访问标记if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || board[x][y] != word[index]) return false;// 标记当前单元格为已访问visited[x][y] = true;path.push_back({x, y});// 遍历上下左右四个方向for (int i = 0; i < 4; i++) {int newX = x + directions[i][0];int newY = y + directions[i][1];if (dfs(board, word, index + 1, newX, newY, visited, path)) return true;}// 回溯，取消当前单元格的访问标记visited[x][y] = false;path.pop_back();return false;
}int main() {int N;cin >> N;vector<vector<char>> board(N, vector<char>(N));// 读取二维字符数组for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> board[i][j];if (j < N - 1) cin.ignore(); // 忽略逗号}}// 读取目标字符串string word;cin >> word;vector<vector<bool>> visited(N, vector<bool>(N, false)); // 访问标记数组vector<pair<int, int>> path; // 记录路径// 遍历整个二维数组，寻找字符串的起始点for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (dfs(board, word, 0, i, j, visited, path)) {// 输出结果for (int k = 0; k < path.size(); k++) {if (k > 0) cout << ",";cout << path[k].first << "," << path[k].second;}return 0;}}}// 如果未找到，输出 Ncout << "N" << endl;return 0;
}JAVA解法：
import java.util.*;public class Main {// 定义方向向量：上下左右private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 深度优先搜索 (DFS) 函数public static boolean dfs(char[][] board, String word, int index, int x, int y, boolean[][] visited, List<int[]> path) {// 如果匹配到目标字符串的最后一个字符，返回 trueif (index == word.length()) {return true;}int n = board.length;// 检查边界条件和访问标记if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || board[x][y] != word.charAt(index)) {return false;}// 标记当前单元格为已访问visited[x][y] = true;path.add(new int[]{x, y});// 遍历上下左右四个方向for (int[] direction : directions) {int newX = x + direction[0];int newY = y + direction[1];if (dfs(board, word, index + 1, newX, newY, visited, path)) {return true;}}// 回溯，取消当前单元格的访问标记visited[x][y] = false;path.remove(path.size() - 1);return false;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取二维数组的大小 Nint N = scanner.nextInt();scanner.nextLine(); // 读取剩余的换行符// 读取二维字符数组char[][] board = new char[N][N];for (int i = 0; i < N; i++) {String[] row = scanner.nextLine().split(",");for (int j = 0; j < N; j++) {board[i][j] = row[j].charAt(0);}}// 读取待查找的字符串String word = scanner.nextLine();boolean[][] visited = new boolean[N][N]; // 访问标记数组List<int[]> path = new ArrayList<>(); // 记录路径// 遍历整个二维数组，寻找字符串的起始点for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (dfs(board, word, 0, i, j, visited, path)) {// 输出结果for (int k = 0; k < path.size(); k++) {if (k > 0) {System.out.print(",");}System.out.print(path.get(k)[0] + "," + path.get(k)[1]);}return;}}}// 如果未找到，输出 NSystem.out.println("N");}
}Python解法：
def dfs(board, word, index, x, y, visited, path):# 如果已经找到整个字符串，返回 Trueif index == len(word):return Truen = len(board)# 检查边界条件和是否已经访问过，以及当前字符是否匹配if x < 0 or y < 0 or x >= n or y >= n or visited[x][y] or board[x][y] != word[index]:return False# 标记当前单元格为已访问visited[x][y] = Truepath.append((x, y))# 方向向量，表示上下左右四个方向directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 遍历四个方向for direction in directions:newX, newY = x + direction[0], y + direction[1]if dfs(board, word, index + 1, newX, newY, visited, path):return True# 回溯：取消当前单元格的访问标记visited[x][y] = Falsepath.pop()return Falsedef find_word(board, word):n = len(board)visited = [[False] * n for _ in range(n)]path = []# 遍历二维数组，查找匹配的起点for i in range(n):for j in range(n):if dfs(board, word, 0, i, j, visited, path):return path# 如果未找到，返回 "N"return "N"# 读取输入
n = int(input().strip())# 读取二维字符数组
board = []
for _ in range(n):board.append(input().strip().split(','))# 读取要查找的字符串
word = input().strip()# 调用函数查找字符串
result = find_word(board, word)# 输出结果
if result == "N":print("N")
else:output = ",".join(f"{x},{y}" for x, y in result)print(output)
