题目描述
小 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;
}