找单词
#回溯#深度优先搜索 2025-04-02 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <ostream>
#include <sstream>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <stack>
using namespace std;

// 需要按照字符串的字符组成顺序搜索，且搜索到的位置必须是相邻单元格
// 其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格

bool DFS(int i,
		 int j,
		 int N,
		 int k,
		 const std::string &word,
		 vector<vector<int>> &path,
		 vector<vector<bool>> &visited,
		 vector<vector<char>> &data) {
	if (i < 0 || i >= N || j < 0 || j >= N || visited[i][j] || word[k] != data[i][j]) {
		return false;
	}
	path.push_back({i, j});
	visited[i][j] = true;
	if (k == word.size() - 1) {    // 找到了字符串
		return true;
	}
	vector<vector<int>> directions = {{0, 1},
									  {0, -1},
									  {1, 0},
									  {-1, 0}};    // 定义四个方向，去搜索相邻的单元格

	for (auto &dir : directions) {
		int newI = i + dir[0];
		int newJ = j + dir[1];
		if (DFS(newI, newJ, N, k + 1, word, path, visited, data)) {
			return true;
		}
	}

	// 回溯
	path.pop_back();
	visited[i][j] = false;
	return false;
}

string findString(const std::string &word, vector<vector<char>> &data, int N) {
	vector<vector<int>> path;
	std::string result;
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (data[i][j] == word[0]) {    // 只有第一个字符相等才有开始搜索的必要
				bool found = DFS(i, j, N, 0, word, path, visited, data);    // 深度搜索查找字符串
				if (found) {
					for (auto &itVec : path) {
						result += to_string(itVec[0]) + "," + to_string(itVec[1]) + ",";
					}
					result.pop_back();    // 移除最后一个多余的 ,
					return result;
				}
			}
		}
	}
	return "N";
}

int main() {

	int N;
	cin >> N;
	cin.ignore();

	vector<vector<char>> data(N, vector<char>(N));
	for (int i = 0; i < N; i++) {
		std::string line;
		getline(cin, line);
		std::istringstream iss(line);
		std::string str;
		int j = 0;
		while (getline(iss, str, ',')) {
			data[i][j] = str[0];
			j++;
		}
	}

	std::string word;
	getline(cin, word);

	cout << findString(word, data, N) << endl;

	return 0;
}

题目说明：

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

水平相邻或垂直相邻的单元格，即可以从当前字符的上下左右开始搜索，并且找到一个连续且符合要求的字符串，明显是深度搜索。

因此，最关键的是 DFS 的实现，由于第一次来做这种题，也是看到如何从四个方向去深度搜索：

1
2
3
4
5
6
7
8
9
10
11
vector<vector<int>> directions = {{0, 1},
								  {0, -1},
								  {1, 0},
								  {-1, 0}};    // 定义四个方向，去搜索相邻的单元格
for (auto &dir : directions) {
	int newI = i + dir[0];
	int newJ = j + dir[1];
	if (DFS(newI, newJ, N, k + 1, word, path, visited, data)) {
		return true;
	}
}

文章推荐：图的存储结构和遍历