题目描述

作为地质学家的JIH,为了绘制地图进行了野外考察。考察结束，他得到了一张n*m的地面高度地图。为了科学研究，JIH定义了一种山峰叫做d-山峰。一个高度为h地点被称作d-山峰，只有满足从这里出发，在不经过小于等于h-d的地点的前提下无法达到比它更高的地方。JIH正纠结于怎么分礼物，标出d-山峰的任务就交给你了。

思路

初见这题想着暴力水分就可以了，但是发现确实是一个暴力，每次bfs时将走过的点标记为一个数t，那么在本次bfs时被标记为t的点就是走过的点，然后随便搞搞就可以了

#include <stdio.h>
#include <queue>
using namespace std;
int n, m, d;
int a[501][501], f[501][501];
int ma = 0, ans = 0;
int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {0, 0, 1, 0, -1};
struct arr
{
    int x, y;
};
int tt = 0;
__attribute__((optimize("-O2")))
int bfs(int x, int y)
{
    tt++;
    queue<arr> t; 
    arr l;
    l.x = x;
    l.y = y;
    t.push(l);
    f[x][y] = tt;
    int fl = 0, h = a[x][y];
    if (h == ma) return 1;
    while (!t.empty())
    {
        arr now = t.front();
        t.pop();
        for (int i = 1; i <= 4; i++)
        {
             if (now.x + dx[i] >=1 && now.x + dx[i] <= n && now.y + dy[i] >= 1 && now.y + dy[i] <= m && (a[now.x + dx[i]][now.y + dy[i]] > h - d) && f[now.x + dx[i]][now.y + dy[i]] != tt)
             {
                    arr to;
                    to.x = now.x + dx[i];
                    to.y = now.y + dy[i];
                    f[to.x][to.y] = tt;
                    t.push(to);
                    if (a[to.x][to.y] > h) return 0;
             }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            if (a[i][j] > ma) ma = a[i][j];
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if(bfs(i, j)) ans++;
        }
    printf("%d\n", ans);
}