题目描述

小 A 最近有了一个口头禅 “呵呵”，于是他给出了一个矩形，让你求出里面有几个 “hehe”（方向无所谓）。

输入格式

第一行两个数 n,m，表示这个矩形的大小。

接下来 n 行，每行 m 个字符，表示这个矩形。

输出格式

一行一个数，表示有几个 “hehe”。

输入输出样例

输入 #1

5 5
heheh
heheh
heheh
heheh
heheh

输出 #1

10

说明/提示

1≤n,m≤1000。

思路

这道题把每个点都当成起点都搜索一下，状态可以拿一个string来存储，每次向后插入一个元素（注意判断边界），判断一下搜出来的结果是不是hehe或eheh，记录答案即可。

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;const int N = 1005;
char str[N][N];
int n, m, ans = 0;void dfs(int x, int y) {string a = "";if (n - x + 1 >= 4) {for (int i = 0; i < 4; i++)a += str[x + i][y];if (a == "hehe" || a == "eheh") ans++;}a = "";if (m - y + 1 >= 4) {for (int i = 0; i < 4; i++)a += str[x][y + i];if (a == "hehe" || a == "eheh") ans++;}
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%s", str[i] + 1);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)dfs(i, j);printf("%d\n", ans);return 0;
}