题目
https://www.acwing.com/problem/content/5168/
题目大意:
给定一个单词和一个字符矩阵,要求找出单词在字符矩阵中出现了多少次。出现定义为:
- 出现在一条直线段上,线段包括水平、垂直、正对角、反对角线段
- 出现在两条垂直相交的直线段上,线段包括水平、垂直、正对角、反对角线段
枚举思路(没做出来)
我一开始的思路就是枚举思路,我画出来了字符串出现的所有可能的情况:
- 直线段一共有4种:水平方向、垂直方向、正对角线方向、反对角线方向
- 转弯线段一共有8种:水平+垂直(共4种)、正对角线+反对角线(共4种)
然后每种情况又包括两种判断:正序遍历判断和倒序遍历判断(两种情况都算出现了这个字符串)。情况统计完了之后,对于直线段还比较容易,按照4种情况遍历就行了。但是对于转弯的情况,发现要写的时候觉得有点麻烦。主要是不知道转弯的时候,变方向的代码要怎么写。
DFS思路
这里参考了y总的思路,用dfs来写。首先遍历起点,对于每个点来说,有8个方向可以走。对于接下来的每一步来说,有两种情况,转弯和不转弯。具体来说:
- 不转弯:沿着当前方向遍历一步
- 转弯:先转弯90度,然后沿着新的方向遍历一步
直到走过的步数恰好等于单词w的长度,此时说明单词出现了一次,答案加1。
时间复杂度分析
- 遍历起点: R ∗ C = 100 ∗ 100 R * C = 100 * 100 R∗C=100∗100
- 遍历8个方向: 8 8 8
- 转弯和不转弯:单词最长有6个字母,不转弯的情况只有 1 1 1种,转弯的情况有 ( 6 − 1 ) ∗ 2 (6-1)* 2 (6−1)∗2种(6个字母,5个转弯点,每个点有两个转弯方向)
所以程序语句执行总次数最多为 100 ∗ 100 ∗ 8 ∗ ( 5 ∗ 2 + 1 ) 100 * 100 * 8 * (5 * 2 + 1) 100∗100∗8∗(5∗2+1),数量级为 1 0 6 10^6 106,小于 1 0 8 10^8 108,不会TLE。
代码细节
首先8个方向用两个增量数组来存:
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
对于转弯来说,如果当前方向编号为d,转弯后的方向编号为new_d,则:
new_d = d ^ 2 ^ (i << 2)
图示如下(图片来自y总视频讲解https://www.acwing.com/video/4876/):
说明:
随便拿一组转弯的点来说明:方向0、方向6、方向2,它们对应的二进制分别为:
- 方向0:000
- 方向6:110
- 方向2:010
将方向0变成方向6或者方向2,可以发现从右往左数,第1位是不变的,第2位进行亦或,第3位变成方向6的时候亦或、变成方向2的时候不变。用二进制表示就是d ^ 2 ^ (i << 2)
,当i等于0的时候第3位不变,当i等于1的时候第3位亦或。(没做过这种题,表示真的很难想到。。。)
对于dfs函数来说,有5个参数:
- x:x坐标
- y:y坐标
- d:方向编号
- u:dfs到单词w的第几个字符了
- turned:是否转过弯了
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110;
string w;
int r, c;
char g[N][N];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
int ans;
void dfs(int x, int y, int d, int u, bool turned) {
/*
走出下一步的时候,分几种情况:
1. 往哪个方向走
2. 是否转弯走
*/
// x, y表示坐标; d表示方向编号; u表示dfs到第几个字符了; turned表示是否转弯了
if (x < 0 || x >= r || y < 0 || y >= c) return ; // 越界
if (g[x][y] != w[u]) return ; // 字符不相同
if (u == w.size() - 1) ans ++ ;
else {
// 不转弯
dfs(x + dx[d], y + dy[d], d, u + 1, turned);
// 转弯
if (u > 0 && !turned) {
// 这里判断转弯的时候,要加一个判断u>0,即从第2个字符开始判断转弯,第一个字符是不能转弯的
for (int i = 0; i < 2; i ++ ) {
int new_d = d ^ 2 ^ (i << 2);
dfs(x + dx[new_d], y + dy[new_d], new_d, u + 1, true);
}
}
}
}
int main() {
cin >> w;
cin >> r >> c;
getchar();
for(int i = 0; i < r; i ++ ) {
for(int j = 0; j < c; j ++ ) {
scanf("%c ", &g[i][j]);
}
}
for(int i = 0; i < r; i ++ ) { // 遍历起点x坐标
for(int j = 0; j < c; j ++ ) { // 遍历起点y坐标
for(int d = 0; d < 8; d ++ ) { // 遍历8个方向
dfs(i, j, d, 0, false);
}
}
}
cout << ans << endl;
return 0;
}
总结
8个方向的方向数组:
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
对于方向编号d(方向编号从0编号到7)来说,旋转90°得到的新的方向编号new_d:
d ^ 2 ^ (0 << 2) // 顺时针旋转90°
d ^ 2 ^ (1 << 2) // 逆时针旋转90°
参照这个结论,应该也能类似地推出旋转180°、沿y轴镜像、沿x轴镜像,由于这个题没用到,我就不写了。