UVA12130 Summits(BFS + 贪心)

UVA12130 Summits(BFS + 贪心)

题目大意：
给你一个h ∗ w 的矩阵，矩阵的每一个元素都有一个值，代表这个位置的高度。

题目要求你找出这个图中有多少个位置是峰值点。从每一个点（高度H）出发遍历这个图有一个要求。就是走过的点的高度不能小于等于H – d；成为峰值点的要求就是从这个点出发走到的位置不能有高度大于H的。

解题思路：
由于图非常大。用dfs肯定不行。将这些点依照高度从大到小的排序。然后每一个点作为起点来遍历，假设找到比这个点大的点就说明不是峰值点。

而且遍历的过程中就会将途中走过的点标记上它能到的最大高度。假设下次要找的这个点已经被标记过了。就说明这个点能够到达更大的高度。肯定不是峰值点，就不须要遍历。

代码：

<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span> <cstdio></cstdio></span>
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span> <cstring></cstring></span>
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span> <algorithm></algorithm></span>

<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn = <span class="hljs-number">505</span>;

<span class="hljs-keyword">int</span> G[maxn][maxn];
<span class="hljs-keyword">int</span> vis[maxn][maxn];
<span class="hljs-keyword">int</span> n, m, d;

<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> dir[<span class="hljs-number">4</span>][<span class="hljs-number">2</span>] = {{<span class="hljs-number">0</span>, -<span class="hljs-number">1</span>}, {<span class="hljs-number">0</span>, <span class="hljs-number">1</span>}, {-<span class="hljs-number">1</span>, <span class="hljs-number">0</span>}, {<span class="hljs-number">1</span>, <span class="hljs-number">0</span>}};

<span class="hljs-keyword">struct</span> Node {

    <span class="hljs-keyword">int</span> x, y, v;
}node[maxn * maxn], q[maxn * maxn];

<span class="hljs-keyword">int</span> cmp (<span class="hljs-keyword">const</span> Node &a, <span class="hljs-keyword">const</span> Node &b) {
    <span class="hljs-keyword">return</span> a.v > b.v;
}

<span class="hljs-keyword">int</span> BFS (<span class="hljs-keyword">int</span> k) {

    <span class="hljs-keyword">int</span> front , rear;
    <span class="hljs-keyword">int</span> cnt = <span class="hljs-number">1</span>;
    front = <span class="hljs-number">0</span>;
    rear = <span class="hljs-number">1</span>;
    q[front] = node[k];
    vis[node[k].x][node[k].y] = node[k].v;
    <span class="hljs-keyword">bool</span> flag = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">while</span> (front < rear) {

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < <span class="hljs-number">4</span>; i++) {

            <span class="hljs-keyword">int</span> newx = q[front].x + dir[i][<span class="hljs-number">0</span>];
            <span class="hljs-keyword">int</span> newy = q[front].y + dir[i][<span class="hljs-number">1</span>];
            <span class="hljs-keyword">if</span> (newx < <span class="hljs-number">0</span> || newx >= n || newy < <span class="hljs-number">0</span> || newy >= m)
                <span class="hljs-keyword">continue</span>;

            <span class="hljs-keyword">if</span> (G[newx][newy] > node[k].v) {
                flag = <span class="hljs-number">0</span>;
                <span class="hljs-keyword">continue</span>;
            }
            <span class="hljs-keyword">if</span> (vis[newx][newy] == node[k].v || node[k].v - G[newx][newy] >= d)
                <span class="hljs-keyword">continue</span>;
            vis[newx][newy] = node[k].v;
            <span class="hljs-keyword">if</span> (G[newx][newy] == node[k].v)
                cnt++;
            <span class="hljs-keyword">else</span>
                G[newx][newy] = node[k].v;
            q[rear].x = newx;
            q[rear++].y = newy;
        }
        front++;
    }
    <span class="hljs-keyword">if</span> (flag)
        <span class="hljs-keyword">return</span> cnt;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

<span class="hljs-keyword">int</span> main () {

    <span class="hljs-keyword">int</span> T;
    <span class="hljs-built_in">scanf</span> (<span class="hljs-string">"%d"</span>, &T);
    <span class="hljs-keyword">while</span> (T--) {

        <span class="hljs-built_in">scanf</span> (<span class="hljs-string">"%d%d%d"</span>, &n, &m, &d);
        <span class="hljs-keyword">int</span> cnt = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < n; i++)
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j < m; j++) {
                <span class="hljs-built_in">scanf</span> (<span class="hljs-string">"%d"</span>, &G[i][j]);
                node[cnt].x = i;
                node[cnt].y = j;
                node[cnt++].v = G[i][j];
            }

        sort (node, node + cnt, cmp);
        <span class="hljs-built_in">memset</span> (vis, -<span class="hljs-number">1</span>, <span class="hljs-keyword">sizeof</span> (vis));
        <span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < cnt; i++) {
            <span class="hljs-keyword">if</span> (vis[node[i].x][node[i].y] == -<span class="hljs-number">1</span>) {
                ans += BFS(i);
            }
        }

        <span class="hljs-built_in">printf</span> (<span class="hljs-string">"%d\n"</span>, ans);
    }
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

Original: https://www.cnblogs.com/hrhguanli/p/5121133.html
Author: hrhguanli
Title: UVA12130 Summits(BFS + 贪心)