【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 找单词(200分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
https://app5938.acapp.acwing.com.cn/contest/1/problem/OD1088
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~
🍓OJ题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- 🌸 找单词
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例解释
- 数据范围
- 题解
🌸 找单词
问题描述
给定一个字符串和一个二维字符数组,要求判断该字符串是否存在于数组中。如果存在,则按字符串字符顺序输出每个字符所在单元格的位置下标字符串;如果找不到则返回 “N”。搜索路径必须按照字符串字符顺序,且只能在水平或垂直相邻的单元格中移动。同一个单元格内的字符不能重复使用。假设在数组中最多只存在一个可能的匹配。
输入格式
第一行是一个整数 n n n,表示二维数组的行数和列数。
接下来的 n n n 行为一个由大写字符组成的二维数组,字符之间用逗号分隔。
最后一行为待查找的字符串,由大写字符组成。
二维数组的大小为 n × n n \times n n×n,其中 0 < n ≤ 100 0 < n \leq 100 0<n≤100。
单词长度为 k k k,其中 0 < k < 1000 0 < k < 1000 0<k<1000。
输出格式
如果能找到该字符串,输出每个位置的下标,并用逗号分隔。
否则,输出 “N”。
样例输入
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
样例解释
在二维数组中找到字符串 “ACCESS” 的路径,按顺序输出各字符的下标。
数据范围
二维数组的大小为 n × n n \times n n×n,其中 0 < n ≤ 100 0 < n \leq 100 0<n≤100。
单词长度为 k k k,其中 0 < k < 1000 0 < k < 1000 0<k<1000。
题解
为了解决这个问题,我们需要在一个二维字符数组中搜索一个给定的字符串,找到该字符串后输出每个字符的坐标。使用深度优先搜索(DFS)来实现这一目标。DFS 通过递归搜索相邻的单元格,检查当前路径是否匹配目标字符串。
在实现中,我们会从每个可能的起始点开始,进行 DFS 搜索,并在每一步记录当前字符的坐标。如果找到了完整的字符串,就输出路径;否则,继续搜索直到找完所有可能的起始点。如果最终没有找到匹配的路径,就输出 “N”。参考代码
- Python
def find_word(grid, word):n = len(grid)vis = [[False] * n for _ in range(n)]directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]def dfs(cnt, x, y, path):if x < 0 or x >= n or y < 0 or y >= n or vis[x][y] or grid[x][y] != word[cnt]:return Falseif cnt == len(word) - 1:print(",".join(f"{i},{j}" for i, j in path))return Truevis[x][y] = Truefor dx, dy in directions:a, b = x + dx, y + dypath.append((a, b))if dfs(cnt + 1, a, b, path):return Truepath.pop()vis[x][y] = Falsereturn Falsefor i in range(n):for j in range(n):if grid[i][j] == word[0]:if dfs(0, i, j, [(i, j)]):returnprint("N")n = int(input())
grid = [input().split(',') for _ in range(n)]
word = input().strip()
find_word(grid, word)
- Java
import java.util.*;public class Main {static int n;static char[][] grid;static String word;static boolean[][] vis;static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();sc.nextLine();grid = new char[n][n];vis = new boolean[n][n];for (int i = 0; i < n; i++) {String[] line = sc.nextLine().split(",");for (int j = 0; j < n; j++) {grid[i][j] = line[j].charAt(0);}}word = sc.nextLine();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == word.charAt(0)) {if (dfs(0, i, j, new ArrayList<>(List.of(new int[]{i, j})))) {return;}}}}System.out.println("N");}private static boolean dfs(int cnt, int x, int y, List<int[]> path) {if (x < 0 || x >= n || y < 0 || y >= n || vis[x][y] || grid[x][y] != word.charAt(cnt)) {return false;}if (cnt == word.length() - 1) {for (int i = 0; i < path.size(); i++) {System.out.print(path.get(i)[0] + "," + path.get(i)[1]);if (i < path.size() - 1) System.out.print(",");}return true;}vis[x][y] = true;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];path.add(new int[]{a, b});if (dfs(cnt + 1, a, b, path)) {return true;}path.remove(path.size() - 1);}vis[x][y] = false;return false;}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
int n;
string s;
bool vis[N][N];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};bool dfs(int cnt, int x, int y, vector<pair<int, int>> &path) {if (x < 0 || x >= n || y < 0 || y >= n || vis[x][y] || g[x][y] != s[cnt])return false;if (cnt == s.size() - 1) {for (int i = 0; i < path.size(); i++) {printf("%d,%d", path[i].first, path[i].second);if (i < path.size() - 1)printf(",");}return true;}vis[x][y] = true;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];path.push_back({a, b});if (dfs(cnt + 1, a, b, path))return true;path.pop_back();}vis[x][y] = false;return false;
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {string t;cin >> t;for (int j = 0; j < n; j++) {g[i][j] = t[j * 2];}}cin >> s;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (g[i][j] == s[0]) {memset(vis, 0, sizeof(vis));vector<pair<int, int>> path = {{i, j}};if (dfs(0, i, j, path)) {return 0;}}}}cout << "N" << endl;return 0;
}