【算法 | 实验18】在字符矩阵中查找给定字符串的所有匹配项

---

题目描述

题目
在字符矩阵中查找给定字符串的所有匹配项
给定一个M×N字符矩阵，以及一个字符串S，找到在矩阵中所有可能的连续字符组成的S的次数。所谓的连续字符，是指一个字符可以和位于其上下左右，左上左下，右上右下8个方向的字符组成字符串。用回溯法求解。

输入描述
输入整数t表示测试用例个数
每个测试用例，输入整数M,N，表示矩阵的行数和列数。
接下来输入M行，每行输入N列个字符
第M+1行输入一个需要在矩阵中查找的字符串S
输出描述
输出t行，每行表示第t个测试用例中矩阵中字符串出现的次数

样例输入
1
5 5
D E M X B
A O E P E
D D C O D
E B E D S
C P Y E N
CODE
样例输出
8
样例解析，有一个测试样例，给定一个5行5列字符矩阵，要查找的字符串是CODE
输出为8表示矩阵中总共包含8个"CODE"，如下所示，括号内为字符对应的行和列。
‘C’(2, 2) ‘O’(1, 1) ‘D’(0, 0) ‘E’(0, 1)
‘C’(2, 2) ‘O’(1, 1) ‘D’(2, 0) ‘E’(3, 0)
‘C’(2, 2) ‘O’(1, 1) ‘D’(2, 1) ‘E’(1, 2)
‘C’(2, 2) ‘O’(1, 1) ‘D’(2, 1) ‘E’(3, 0)
‘C’(2, 2) ‘O’(1, 1) ‘D’(2, 1) ‘E’(3, 2)
‘C’(2, 2) ‘O’(2, 3) ‘D’(2, 4) ‘E’(1, 4)
‘C’(2, 2) ‘O’(2, 3) ‘D’(3, 3) ‘E’(3, 2)
‘C’(2, 2) ‘O’(2, 3) ‘D’(3, 3) ‘E’(4, 3)

---

思路分析

和经典的回溯法走迷宫很像，比较不同的是：
1、有 8 个行走方向
2、需要统计能匹配目标字符串的路径的数量

关于 8 个行走方向，我差点就要上 8 个if了，好在及时想到了可以使用循环。

统计路径数：设从某个位置出发，能和目标字符串 S 的剩余部分匹配的路径数为 $f$；从该位置周围的 8 个位置出发，能和目标字符串 S 的剩余部分匹配的路径数分别为 $x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$，则：
$$f=x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8$$
例如在下图中，以中间的$C$为当前位置，则$x_1=5,x_4=3$，其余 x 为 0，$f=5+3=8$。

---

bug记录：“error: ‘>>’ should be ‘> >’ within a nested template argument list”

中文翻译：“错误：”>>“在嵌套模板参数列表中应为”> >”

// 错误代码
vector<vector<char>>
// 修改方案：在两个尖括号中加个空格
vector<vector<char> >
1
2
3
4

原因：在使用C++11之前标准的编译器将">>“视为移位符号,导致编译错误
参考：https://blog.csdn.net/yiti8689/article/details/108134804

---

代码

OJ成功通过了

#include
#include
#include
#include
using namespace std;


//判断i, j是否在矩阵内 
bool inside(int i, int j, int m, int n){
	if(0 <= i && i < m && 0 <= j && j < n){
		return true;
	}
	return false;
}

// 回溯实现
// 参数，i,j为当前位置；len为已成功匹配的字符个数；s为目标字符串； 
int hui_su(vector<vector<char> > a, int i, int j, int m, int n, int len, string s){
	if(a[i][j] != s[len]){
		return 0;
	}
	else {
		len++;
		if(s.length() == len){
			return 1;
		}
	}
	
	//向8个方向搜索 
	int count = 0;
	for(int x = -1; x <= 1; x++){
		for(int y = -1; y <= 1; y++){
			if(x == 0 && y == 0){
				continue;
			}
			if(inside(i+x, j+y, m, n)){
				count += hui_su(a, i+x, j+y, m, n, len, s);
			}
		}
	}
	return count;
}


int main(){
	int t;  //测试用例个数
	cin >> t; 
	
	// 输入
	for(int k = 0; k < t; k++){
		int m, n;  //矩阵的大小
		string s;  //目标字符串 
		cin >> m >> n;
		vector<vector<char> > a(m, vector<char>(n));  //矩阵
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				cin >> a[i][j];
			}
		} 
		cin >> s;

		int count = 0;
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				count += hui_su(a, i, j, m, n, 0, s);
			}
		}
		cout << count;
	} 
	return 0;
}
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

---

完