3 4
A B C E
S F C S
A D E E
ABCCED

true

3 4
A B C E
S F C S
A D E E
SEE

true

3 4
A B C E
S F C S
A D E E
ABCB

false

def exist(board, word):
    # 获取网格行数和列数
    m, n = len(board), len(board[0])
    
    def dfs(i, j, index):
        # 当索引达到单词长度时，匹配成功
        if index == len(word):
            return True
        # 检查边界条件和当前单元格字符是否匹配
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[index]:
            return False
        # 暂存当前字符，并标记为已访问，避免重复使用
        temp = board[i][j]
        board[i][j] = '#'
        # 递归搜索四个方向：下、上、右、左
        found = dfs(i + 1, j, index + 1) or dfs(i - 1, j, index + 1) or \
                dfs(i, j + 1, index + 1) or dfs(i, j - 1, index + 1)
        # 恢复现场
        board[i][j] = temp
        return found
    
    # 遍历每个单元格作为起点
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True
    return False

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        exit(0)
    # 第一个和第二个数字分别为网格的行数和列数
    m = int(input_data[0])
    n = int(input_data[1])
    board = []
    index = 2
    # 读取二维网格数据
    for _ in range(m):
        row = []
        for _ in range(n):
            row.append(input_data[index])
            index += 1
        board.append(row)
    # 读取单词
    word = input_data[index]
    # 输出结果，true 表示存在，false 表示不存在
    print("true" if exist(board, word) else "false")

import java.util.Scanner;

public class Main {
    // 主函数，从标准输入中读取数据（ACM模式）
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取网格的行数 m 和列数 n
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine(); // 消耗换行符
        
        // 构造二维字符数组 board
        char[][] board = new char[m][n];
        for (int i = 0; i < m; i++) {
            String line = sc.nextLine();
            String[] tokens = line.split("\\s+");
            for (int j = 0; j < n; j++) {
                board[i][j] = tokens[j].charAt(0);
            }
        }
        // 读取要搜索的单词
        String word = sc.nextLine();
        // 输出结果：true 表示存在，false 表示不存在
        System.out.println(exist(board, word) ? "true" : "false");
        sc.close();
    }
    
    // 判断单词是否存在于网格中的函数
    public static boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        // 遍历每个单元格作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 深度优先搜索（DFS）函数
    private static boolean dfs(char[][] board, String word, int i, int j, int index) {
        // 当索引达到单词长度时，匹配成功
        if (index == word.length()) {
            return true;
        }
        // 检查边界条件以及当前单元格字符是否匹配
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }
        // 暂存当前字符，并标记为已访问
        char temp = board[i][j];
        board[i][j] = '#';
        // 递归搜索四个方向：下、上、右、左
        boolean found = dfs(board, word, i + 1, j, index + 1)
                     || dfs(board, word, i - 1, j, index + 1)
                     || dfs(board, word, i, j + 1, index + 1)
                     || dfs(board, word, i, j - 1, index + 1);
        // 恢复当前单元格字符
        board[i][j] = temp;
        return found;
    }
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 深度优先搜索（DFS）函数，判断从 (i, j) 出发能否匹配单词中从 index 开始的字符
bool dfs(vector<vector<char>>& board, const string& word, int i, int j, int index) {
    // 如果 index 等于单词长度，说明全部匹配成功
    if (index == word.size()) return true;
    // 检查边界条件以及当前单元格字符是否匹配
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index])
        return false;
    // 暂存当前字符，并标记为已访问
    char temp = board[i][j];
    board[i][j] = '#';
    // 递归搜索四个方向：下、上、右、左
    bool found = dfs(board, word, i + 1, j, index + 1)
              || dfs(board, word, i - 1, j, index + 1)
              || dfs(board, word, i, j + 1, index + 1)
              || dfs(board, word, i, j - 1, index + 1);
    // 恢复当前单元格字符
    board[i][j] = temp;
    return found;
}

int main() {
    int m, n;
    // 读取网格的行数和列数
    cin >> m >> n;
    vector<vector<char>> board(m, vector<char>(n));
    // 读取二维字符网格数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    // 读取要搜索的单词
    string word;
    cin >> word;
    
    // 遍历每个单元格作为起点
    bool exists = false;
    for (int i = 0; i < m && !exists; i++) {
        for (int j = 0; j < n && !exists; j++) {
            if (dfs(board, word, i, j, 0)) {
                exists = true;
            }
        }
    }
    // 输出结果：true 表示存在，false 表示不存在
    cout << (exists ? "true" : "false") << endl;
    return 0;
}