1111.【搜索与回溯算法】保卫农场

时间限制: 1 s

空间限制: 256 MB

题目描述

农夫John的农场里有很多小山丘，他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话，他总共需要招聘多少名保镖。他现在有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。

小山丘的定义是：若地图中一个元素所邻接的所有元素都比这个元素高度要小或等于（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘（本题某个非边界点跟它相邻的有8个点：上、下、左、右、左上、右上、左下、右下）。

输入

第1行：两个由空格隔开的整数N和M；

第2行到第N+1行：

第I+l行描述了地图上的第I行，有M个由空格隔开的整数：H_ij。

输出

一个整数，表示小山丘的个数。

样例输入

8 7

4 3 2 2 1 0 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 1 1 0 0

1 1 0 0 0 1 0

0 0 0 1 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

样例输出

3

感觉我做得不对，还有些荒谬......

上代码！

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, a[107][107], vis[107][107];
void dfs (int);
int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			scanf ("%d", &a[i][j]);
	}
	dfs (1);
	printf ("%d", ans);
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//			printf ("%d ", vis[i][j]);
//		printf ("\n");
//	}
	return 0;
}
void dfs (int x)
{
	for (int i = 1; i <= m; i++)
	{
		if (a[x - 1][i] <= a[x][i] && a[x + 1][i] <= a[x][i] && a[x][i - 1] <= a[x][i]
		    && a[x][i + 1] <= a[x][i] && a[x - 1][i - 1] <= a[x][i] && a[x - 1][i + 1] <= a[x][i]
			&& a[x + 1][i - 1] <= a[x][i] && a[x + 1][i + 1] <= a[x][i])
			{
				if (vis[x - 1][i] == 0 && vis[x + 1][i] == 0 && vis[x][i - 1] == 0
				    && vis[x][i + 1] == 0 && vis[x - 1][i - 1] == 0 && vis[x - 1][i + 1] == 0
					&& vis[x + 1][i - 1] == 0 && vis[x + 1][i + 1] == 0)
					{
						vis[x][i] = 1;
						vis[x - 1][i] = 1;
						vis[x + 1][i] = 1;
						vis[x][i - 1] = 1;
					    vis[x][i + 1] = 1;
						vis[x - 1][i - 1] = 1;
						vis[x - 1][i + 1] = 1;
						vis[x + 1][i - 1] = 1;
						vis[x + 1][i + 1] = 1;
						ans++;
						dfs (x + 1);
					}
			}
	}
}

是不是很荒谬......