E-找单词(100p)

刷题笔记合集🔗

找单词

问题描述

给定一个字符串和一个二维字符数组，要求判断该字符串是否存在于数组中。如果存在，则按字符串字符顺序输出每个字符所在单元格的位置下标字符串；如果找不到则返回 "N"。搜索路径必须按照字符串字符顺序，且只能在水平或垂直相邻的单元格中移动。同一个单元格内的字符不能重复使用。假设在数组中最多只存在一个可能的匹配。

输入格式

第一行是一个整数 $n$ ，表示二维数组的行数和列数。

接下来的 $n$ 行为一个由大写字符组成的二维数组，字符之间用逗号分隔。

最后一行为待查找的字符串，由大写字符组成。

二维数组的大小为 $n \times n$ ，其中 $0 < n \leq 100$ 。

单词长度为 $k$ ，其中 $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 \times n$ ，其中 $0 < n \leq 100$ 。

单词长度为 $k$ ，其中 $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 False
        if cnt == len(word) - 1:
            print(",".join(f"{i},{j}" for i, j in path))
            return True

        vis[x][y] = True
        for dx, dy in directions:
            a, b = x + dx, y + dy
            path.append((a, b))
            if dfs(cnt + 1, a, b, path):
                return True
            path.pop()
        vis[x][y] = False
        return False

    for i in range(n):
        for j in range(n):
            if grid[i][j] == word[0]:
                if dfs(0, i, j, [(i, j)]):
                    return
    print("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;
    }
}

#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;
}

#刷题#