思路：DFS

本题改编自LeetCode原题：79. 单词搜索 - 力扣（LeetCode）

比LeetCode这道题多了一个保存路径，首先，我们可以定义一个长度为4的数组来表示上下左右四个方向，然后我们可以判断分别从每一个位置为起点，是否能够构成一个路径使得和目标字符串相等，我们可以一边走一边存储当前的路径，比如对于C++选手可以维护一个vector<pair<int,int>>去表示路径，对于Python选手可以维护一个元组去表示路径，这里需要注意，如果回溯的话需要对遍历过的路径进行删除，具体可以参考下方代码和注释，写的很详细。

JavaScript

const N = 1010;
// 二维数组 g 用于存储字符迷宫
const g = Array.from(Array(N), () => Array(N).fill(''));
let n = 0;
let s = '';
// 用于记录位置是否被访问过的数组 vis
let vis = Array.from(Array(N), () => Array(N).fill(false));
// 方向数组，分别表示上、下、右、左
const dx = [-1, 1, 0, 0];
const dy = [0, 0, 1, -1];

// 深度优先搜索函数，用于在迷宫中寻找字符串 s 的路径
function dfs(cnt, x, y, path) {
    // 判断是否越界、已访问或者当前位置字符不匹配
    if (x < 0 || x >= n || y < 0 || y >= n || vis[x][y] || g[x][y] !== s[cnt]) {
        return false;
    }

    // 如果已经找到字符串的最后一个字符，输出路径并返回 true
    if (cnt === s.length - 1) {
        console.log(path.map(pair => `${pair[0]},${pair[1]}`).join(','));
        return true;
    }

    // 标记当前位置已访问
    vis[x][y] = true;

    // 遍历四个方向
    for (let i = 0; i < 4; i++) {
        const a = dx[i] + x;
        const b = dy[i] + y;
        // 记录路径
        path.push([a, b]);
        // 递归调用 dfs
        if (dfs(cnt + 1, a, b, path)) {
            return true;
        }
        // 回溯，恢复路径
        path.pop();
    }

    // 恢复当前位置未访问状态
    vis[x][y] = false;
    return false;
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = 0;
let currentRow = 0;

rl.on('line', (line) => {
    if (inputLines === 0) {
        // 读取迷宫的大小
        n = parseInt(line);
    } else if (inputLines <= n) {
        // 读取迷宫的每一行
        const trimmedRow = line.trim();
        for (let j = 0; j < n; j++) {
            g[currentRow][j] = trimmedRow[j * 2];
        }
        currentRow++;
    } else {
        // 读取目标字符串 s
        s = line.trim();
        // 在迷宫中寻找字符串 s 的路径
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (g[i][j] === s[0]) {
                    vis = Array.from(Array(N), () => Array(N).fill(false));
                    const path = [[i, j]];
                    if (dfs(0, i, j, path)) {
                        // 找到路径后关闭输入
                        rl.close();
                        return;
                    }
                }
            }
        }
        // 如果未找到路径，也关闭输入
        rl.close();
    }
    inputLines++;
});

Java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static char[][] g = new char[N][N];
    static int n = 0;
    static String s = "";
    static boolean[][] vis = new boolean[N][N];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        // 读取迷宫字符数组 g
        for (int i = 0; i < n; i++) {
            String t = scanner.nextLine().trim();
            for (int j = 0; j < n; j++) {
                g[i][j] = t.charAt(j * 2);
            }
        }

        // 读取目标字符串 s
        s = scanner.nextLine().trim();

        // 在迷宫中寻找字符串 s 的路径
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == s.charAt(0)) {
                    vis = new boolean[N][N];
                    ArrayList<Pair> path = new ArrayList<>();
                    path.add(new Pair(i, j));
                    if (dfs(0, i, j, path)) {
                        break;
                    }
                }
            }
        }
    }

    static boolean dfs(int cnt, int x, int y, ArrayList<Pair> path) {
        // 判断是否越界、已访问或者当前位置字符不匹配
        if (x < 0 || x >= n || y < 0 || y >= n || vis[x][y] || g[x][y] != s.charAt(cnt)) {
            return false;
        }

        // 如果已经找到字符串的最后一个字符，输出路径并返回 true
        if (cnt == s.length() - 1) {
            for (int i = 0; i < path.size(); i++) {
                System.out.print(path.get(i).a + "," + path.get(i).b);
                if (i < path.size() - 1) {
                    System.out.print(",");
                }
            }
            System.out.println();
            return true;
        }

        // 标记当前位置已访问
        vis[x][y] = true;

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x;
            int b = dy[i] + y;
            // 记录路径
            path.add(new Pair(a, b));
            // 递归调用 dfs
            if (dfs(cnt + 1, a, b, path)) {
                return true;
            }
            // 回溯，移除路径
            path.remove(path.size() - 1);
        }

        // 恢复当前位置未访问状态
        vis[x][y] = false;
        return false;
    }

    // 定义 Pair 类，用于保存坐标
    static class Pair {
        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

Python

N = 1010
# 二维数组 g 用于存储字符迷宫
g = [['' for _ in range(N)] for _ in range(N)]
n = 0
s = ''
# 用于记录位置是否被访问过的数组 vis
vis = [[False] * N for _ in range(N)]
# 方向数组，分别表示上、下、右、左
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# 深度优先搜索函数，用于在迷宫中寻找字符串 s 的路径
def dfs(cnt, x, y, path):
    global vis
    # 判断是否越界、已访问或者当前位置字符不匹配
    if x < 0 or x >= n or y < 0 or y >= n or vis[x][y] or g[x][y] != s[cnt]:
        return False

    # 如果已经找到字符串的最后一个字符，输出路径并返回 True
    if cnt == len(s) - 1:
        print(','.join(f"{a},{b}" for a, b in path))
        return True

    # 标记当前位置已访问
    vis[x][y] = True

    # 遍历四个方向
    for i in range(4):
        a, b = dx[i] + x, dy[i] + y
        # 记录路径
        path.append((a, b))
        # 递归调用 dfs
        if dfs(cnt + 1, a, b, path):
            return True
        # 回溯，恢复路径
        path.pop()

    # 恢复当前位置未访问状态
    vis[x][y] = False
    return False

# 读取迷宫的大小
n = int(input())

# 读取迷宫的每一行
for i in range(n):
    t = input().strip()
    for j in range(n):
        g[i][j] = t[j * 2]

# 读取目标字符串 s
s = input().strip()

# 在迷宫中寻找字符串 s 的路径
for i in range(n):
    for j in range(n):
        if g[i][j] == s[0]:
            vis = [[False] * N for _ in range(N)]
            path = [(i, j)]
            if dfs(0, i, j, path):
                break

C++

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

    // 如果已经找到字符串的最后一个字符，输出路径并返回 true
    if (cnt == s.size() - 1) {
        int m = path.size();
        for (int i = 0; i < m; i++) {
            printf("%d,%d", path[i].first, path[i].second);
            if (i < m - 1) {
                printf(",");
            }
        }
        return true;
    }

    // 标记当前位置已访问
    vis[x][y] = true;

    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int a = dx[i] + x;
        int b = dy[i] + y;

        // 记录路径
        path.push_back({a, b});

        // 递归调用 dfs
        if (dfs(cnt + 1, a, b, path)) {
            return true;
        }

        // 回溯，移除路径
        path.pop_back();
    }

    // 恢复当前位置未访问状态
    vis[x][y] = false;
    return false;
}

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

    // 读取迷宫字符数组 g
    for (int i = 0; i < n; i++) {
        string t;
        cin >> t;
        for (int j = 0; j < n; j++) {
            g[i][j] = t[j * 2];
        }
    }

    // 读取目标字符串 s
    cin >> s;

    // 在迷宫中寻找字符串 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)) {
                    break;
                }
            }
        }
    }

    return 0;
}

题目描述

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

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

输入描述

第一行一个整数，表示二维数组所占行数。

第二行到第 N+1 行输入为一个二维大写字符数组。并用","分割

第 N + 2 行为待查找的字符串，由大写字符组成。

二维数组的大小为 N × N， 0 < N ≤ 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