返回目录

题目描述

给一个字符串和一个二维字符数组，如果该字符串存在于该数组中，则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串，如果找不到返回字符串“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个字符列下标。

示例：

Python算法源码

# 导入sys模块，用于读取标准输入
import sys

# 存储输入的每一行数据
lines = []
# 存储二维数组的大小
n = None

# 监听命令行输入的每一行数据
for line in sys.stdin:
    # 去除换行符并将每一行数据存入lines数组
    lines.append(line.strip())
    # 如果输入的是二维数组的大小
    if len(lines) == 1:
        n = int(lines[0])
    # 如果输入的是二维数组和待查找的字符串
    if n and len(lines) == n + 2:
        # 删除lines数组中的第一个元素，即二维数组的大小
        lines.pop(0)
        # 将lines数组中的最后一个元素，即待查找的字符串，存入变量str
        tar = lines.pop()
        # 将lines数组中的其余元素，即二维数组的每一行，按逗号分隔存入二维数组grid
        grid = [line.split(",") for line in lines]
      
        # 查找字符串的函数
        def find_string(grid, n, tar):
            # 创建一个n*n的二维数组，所有元素初始化为False，表示没有被访问过
            visited = [[False] * n for _ in range(n)]
            # 存储路径的数组
            path = []

            # 深度优先搜索的函数
            def dfs(i, j, k, path):
                # 如果当前位置越界，或已被访问，或当前位置的字符与待查找字符串的当前字符不相同
                if (
                    i < 0 or i >= n or j < 0 or j >= n or visited[i][j] or tar[k] != grid[i][j]
                ):
                    # 返回False
                    return False
                # 将当前位置添加到路径中
                path.append([i, j])
                # 标记当前位置已被访问
                visited[i][j] = True
                # 如果已经找到了所有的字符
                if k == len(tar) - 1:
                    # 返回True
                    return True
                # 定义四个方向
                directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
                # 对四个方向进行深度优先搜索
                for direction in directions:
                    ni, nj = i + direction[0], j + direction[1]
                    res = dfs(ni, nj, k + 1, path)
                    # 如果在某个方向上找到了字符串
                    if res:
                        # 返回True
                        return True
                # 撤销对当前位置的访问标记
                visited[i][j] = False
                # 从路径中移除当前位置
                path.pop()
                # 返回False
                return False

            # 遍历二维数组的每个单元格
            for i in range(n):
                for j in range(n):
                    # 如果当前单元格的字符与待查找字符串的第一个字符相同
                    if grid[i][j] == tar[0]:
                        # 使用深度优先搜索查找字符串
                        found = dfs(i, j, 0, path)
                        # 如果找到了字符串
                        if found:
                            # 初始化结果字符串
                            result = ""
                            # 将路径中的每个单元格的位置添加到结果字符串中
                            for pos in path:
                                result += str(pos[0]) + "," + str(pos[1]) + ","
                            # 删除最后一个逗号
                            result = result[:-1]
                            # 返回结果字符串
                            return result
            # 如果没有找到字符串，返回"N"
            return "N"

        # 调用find_string函数，输出结果
        print(find_string(grid, n, tar))
        # 清空lines数组
        lines = []

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 100

int n;
char matrix[MAX_SIZE][MAX_SIZE]; // 用于存储字符矩阵
char word[MAX_SIZE]; // 用于存储待搜索的单词
bool used[MAX_SIZE][MAX_SIZE]; // 用于标记字符是否已经被使用过

// 函数：将输入字符串按指定分隔符分割
char* splitCin(char separator) {
    char s[MAX_SIZE];
    scanf("%s", s);

    char* res = (char*)malloc(MAX_SIZE * sizeof(char)); // 分配内存以存储结果
    strcpy(res, ""); // 初始化结果字符串为空

    char* token = strtok(s, &separator); // 使用strtok函数按分隔符分割字符串

    while (token != NULL) {
        strcat(res, token); // 将分割后的子字符串连接到结果字符串中
        token = strtok(NULL, &separator);
    }

    return res; // 返回结果字符串
}

// 函数：深度优先搜索，寻找单词在字符矩阵中的路径
bool dfs(int i, int j, int k, char path[MAX_SIZE][6]) {
    // 边界条件检查：索引超出范围或当前字符不匹配或已经使用过
    if (i < 0 || i >= n || j < 0 || j >= n || matrix[i][j] != word[k] || used[i][j]) {
        return false; // 返回false表示搜索失败
    }

    // 将当前位置坐标添加到路径中
    sprintf(path[k], "%d,%d", i, j);

    // 如果已经匹配到最后一个字符，返回true表示搜索成功
    if (k + 1 == strlen(word)) {
        return true;
    }

    used[i][j] = true; // 将当前位置标记为已使用

    // 递归搜索上下左右相邻的字符
    bool res = dfs(i - 1, j, k + 1, path) || dfs(i + 1, j, k + 1, path) || dfs(i, j - 1, k + 1, path) ||
               dfs(i, j + 1, k + 1, path);

    // 如果搜索失败，重置当前位置的状态和路径
    if (!res) {
        used[i][j] = false;
        path[k][0] = '\0';
    }

    return res; // 返回搜索结果
}

int main() {
    scanf("%d", &n); // 输入字符矩阵的大小

    // 输入字符矩阵
    for (int i = 0; i < n; i++) {
        strcpy(matrix[i], splitCin(',')); // 将逗号分隔的字符串拆分并存储到字符矩阵中
    }

    scanf("%s", word); // 输入待搜索的单词

    // 遍历字符矩阵，开始搜索
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char path[MAX_SIZE][6]; // 存储路径的二维数组
            if (dfs(i, j, 0, path)) { // 如果搜索成功
                // 输出路径
                printf("%s", path[0]);
                for (int k = 1; k < strlen(word); k++) {
                    printf(",%s", path[k]);
                }
                printf("\n");
                return 0;
            }
        }
    }

    printf("N\n"); // 没有找到匹配的路径，输出N

    return 0;
} <stdbool.h>
#include <string.h>

#define MAX_SIZE 100

int n;
char matrix[MAX_SIZE][MAX_SIZE];
char word[MAX_SIZE];
bool used[MAX_SIZE][MAX_SIZE];

char* splitCin(char separator) {
    char s[MAX_SIZE];
    scanf("%s", s);

    char* res = (char*)malloc(MAX_SIZE * sizeof(char));
    strcpy(res, "");

    char* token = strtok(s, &separator);

    while (token != NULL) {
        strcat(res, token);
        token = strtok(NULL, &separator);
    }

    return res;
}

bool dfs(int i, int j, int k, char path[MAX_SIZE][6]) {
    if (i < 0 || i >= n || j < 0 || j >= n || matrix[i][j] != word[k] || used[i][j]) {
        return false;
    }

    sprintf(path[k], "%d,%d", i, j);

    if (k + 1 == strlen(word)) {
        return true;
    }

    used[i][j] = true;

    bool res = dfs(i - 1, j, k + 1, path) || dfs(i + 1, j, k + 1, path) || dfs(i, j - 1, k + 1, path) ||
               dfs(i, j + 1, k + 1, path);

    if (!res) {
        used[i][j] = false;
        path[k][0] = '\0';
    }

    return res;
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        strcpy(matrix[i], splitCin(','));
    }

    scanf("%s", word);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char path[MAX_SIZE][6];
            if (dfs(i, j, 0, path)) {
                printf("%s", path[0]);

                for (int k = 1; k < strlen(word); k++) {
                    printf(",%s", path[k]);
                }

                printf("\n");
                return 0;
            }
        }
    }

    printf("N\n");

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    static int n;  // 二维数组的大小
    static String[][] matrix;  // 二维数组
    static String tar;  // 待查找的字符串
    static boolean[][] visited;  // 记录每个单元格是否已被访问

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();  // 读取二维数组的大小
        scanner.nextLine();  // 忽略换行符
        matrix = new String[n][n];  // 初始化二维数组
        for (int i = 0; i < n; i++) {  // 读取二维数组的每一行
            String line = scanner.nextLine();
            String[] cells = line.split(",");
            matrix[i] = cells;
        }
        tar = scanner.nextLine();  // 读取待查找的字符串

        visited = new boolean[n][n];  // 初始化访问记录数组
        String result = findString();  // 查找字符串
        System.out.println(result);  // 输出结果
    }

    static String findString() {
        List<List<Integer>> path = new ArrayList<>();  // 存储路径的列表
        for (int i = 0; i < n; i++) {  // 遍历二维数组的每个单元格
            for (int j = 0; j < n; j++) {
                if (matrix[i][j].equals(tar.substring(0, 1))) {  // 如果当前单元格的字符与待查找字符串的第一个字符相同
                    boolean found = dfs(i, j, 0, path);  // 使用深度优先搜索查找字符串
                    if (found) {  // 如果找到了字符串
                        StringBuilder result = new StringBuilder();  // 初始化结果字符串
                        for (List<Integer> pos : path) {  // 将路径中的每个单元格的位置添加到结果字符串中
                            result.append(pos.get(0)).append(",").append(pos.get(1)).append(",");
                        }
                        result.deleteCharAt(result.length() - 1);  // 删除最后一个逗号
                        return result.toString();  // 返回结果字符串
                    }
                }
            }
        }
        return "N";  // 如果没有找到字符串，返回"N"
    }

    static boolean dfs(int i, int j, int k, List<List<Integer>> path) {
        // 如果当前位置越界，或已被访问，或当前位置的字符与待查找字符串的当前字符不相同
        if (i < 0 || i >= n || j < 0 || j >= n || visited[i][j] || !tar.substring(k, k + 1).equals(matrix[i][j])) {
            return false;  // 返回false
        }
        List<Integer> pos = new ArrayList<>();
        pos.add(i);
        pos.add(j);
        path.add(pos);  // 将当前位置添加到路径中
        visited[i][j] = true;  // 标记当前位置已被访问
        if (k == tar.length() - 1) {  // 如果已经找到了所有的字符
            return true;  // 返回true
        }
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // 定义四个方向
        for (int[] direction : directions) {  // 对四个方向进行深度优先搜索
            int ni = i + direction[0];
            int nj = j + direction[1];
            boolean res = dfs(ni, nj, k + 1, path);
            if (res) {  // 如果在某个方向上找到了字符串
                return true;  // 返回true
            }
        }
        visited[i][j] = false;  // 撤销对当前位置的访问标记
        path.remove(path.size() - 1);  // 从路径中移除当前位置
        return false;  // 返回false
    }
}