【luogu P2919 [USACO08NOV]守护农场Guarding the Farm】 题解

题目链接：https://www.luogu.org/problemnew/show/P2919

1.搜索的时候分清楚全局变量和局部变量的区别

2.排序优化搜索

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 2000;

const int inf = 0x7fffffff;

int map[maxn][maxn], n, m, ans, cnt, tot;

bool vis[maxn][maxn];

struct hail{

    int x, y, h;

}f[maxn * maxn];

bool cmp(hail a, hail b)

{

    return a.h > b.h;

}

void dfs1(int x, int y)

{

    tot++;

    vis[x][y] = 1;

    if(map[x][y] >= map[x+1][y] && vis[x+1][y] == 0) dfs1(x+1, y);

    if(map[x][y] >= map[x-1][y] && vis[x-1][y] == 0) dfs1(x-1, y);

    if(map[x][y] >= map[x+1][y+1] && vis[x+1][y+1] == 0) dfs1(x+1, y+1);

    if(map[x][y] >= map[x+1][y-1] && vis[x+1][y-1] == 0) dfs1(x+1, y-1);

    if(map[x][y] >= map[x-1][y+1] && vis[x-1][y+1] == 0) dfs1(x-1, y+1);

    if(map[x][y] >= map[x-1][y-1] && vis[x-1][y-1] == 0) dfs1(x-1, y-1);

    if(map[x][y] >= map[x][y+1] && vis[x][y+1] == 0) dfs1(x, y+1);

    if(map[x][y] >= map[x][y-1] && vis[x][y-1] == 0) dfs1(x, y-1);

}

int main()

{

    scanf("%d%d",&n,&m);

	for(int i = 0; i <= n + 1; i++)

		for(int j = 0; j <= m + 1; j++)vis[i][j] = 1;

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++)

        scanf("%d",&map[i][j]), f[++cnt].x = i, f[cnt].y = j, f[cnt].h = map[i][j], vis[i][j] = 0;

    sort(f+1, f+1+n*m, cmp);

    cnt = 0;

    while(tot < n * m)

    {

        ans++;

        while(vis[f[cnt].x][f[cnt].y] == 1) cnt++;

        dfs1(f[cnt].x, f[cnt].y);

        for(int i = 1; i <= n; i++)

        {for(int j = 1; j <= m; j++)

    		cout<<vis[i][j]<<" ";

    		cout<<endl;

		}

		cout<<endl;

	}

    printf("%d",ans);

    return 0;

}