E2-13.找单词（dfs）

题目描述

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

用例1

输入

4
A,C,C,F
C,D,E,D
B,E,S,S
F,E,C,A
ACCESS

Copy

输出

0,0,0,1,0,2,1,2,2,2,2,3

Copy

说明

ACCESS分别对应二维数组的[0,0] [0,1] [0,2] [1,2] [2,2] [2,3]下标位置。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e3 + 10;
int n;
string word;
vector<vector<char>> grid;
vector<vector<bool>> visited;
int dirX[] = {-1, 1, 0, 0};
int dirY[] = {0, 0, -1, 1};
// 深搜
bool dfs(int x, int y, int index, vector<pair<int, int>>& path) {
    // 如果已经找到整个字符串
    if (index == word.length()) {
        return true;
    }
    if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] != word[index]) {
        return false;
    }
    // 标记当前单元格为访问过
    visited[x][y] = true;
    path.push_back({x, y});  // 记录当前字符的位置
    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int newX = x + dirX[i];
        int newY = y + dirY[i];
        if (dfs(newX, newY, index + 1, path)) {
            return true;
        }
    }
    // 回溯，恢复状态
    visited[x][y] = false;
    path.pop_back();
    return false;
}
void solve() {
    cin >> n; 
   //恶心的输入
    grid.resize(n, vector<char>(n));  
    visited.resize(n, vector<bool>(n, false));  
    string line;
    getline(cin, line);  
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        stringstream ss(line);
        char c;
        for (int j = 0; j < n; j++) {
            ss >> c;  
            grid[i][j] = c;  
            if (ss.peek() == ',') ss.ignore(); 
        }
    }
    cin >> word;
    vector<pair<int, int>> path;  
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == word[0]) {  // 找到第一个字符
                if (dfs(i, j, 0, path)) {  // 尝试深度优先搜索
                    // 输出路径
                    for (int k = 0; k < path.size(); k++) {
                        if (k != 0) cout << ",";
                        cout << path[k].first << "," << path[k].second;
                    }
                    return;  // 找到就返回
                }
            }
        }
    }
    cout << "N" << endl;
}

signed main() {
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();  
    }
    return 0;
}