洛谷P1234题解

题目描述

小 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;
}