BZOJ1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 （BFS）
1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 661 Solved: 292 [Submit][Status][Discuss]
Description
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map. A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
农夫JOHN的农夫上有很多小山丘，他想要在那里布置一些保镖（……）去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话，他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是：若地图中一个元素所邻接的所有元素都比这个元素高度要小（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1，则称这两个元素邻接。 问题名称：guard 输入格式： 第一行：两个由空格隔开的整数N和M 第二行到第N+1行：第I+1行描述了地图上的第I行，有M个由空格隔开的整数：H_ij.
Input
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
Output
- Line 1: A single integer that specifies the number of hilltops
Sample Input
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
Sample Output
3
HINT
三个山丘分别是：左上角的高度为4的方格，右上角的高度为1的方格，还有最后一行中高度为2的方格．
Source
[Submit][Status][Discuss] HOME Back\
题目的中文描述的数据范围有问题！
题目的中文描述的数据范围有问题！
题目的中文描述的数据范围有问题！
思路：BFS,我的做法是预处理所有“坏点”，也就是如果点（i,j）的相邻点中有比点（i,j）高的，那么点(i,j)就是坏点。
然后bfs的时候，对于存在一个坏点的联通块（只有数字相同的点能构成一个联通块）都标记成坏点。
然后用左上角开始做bfs…注意遇到坏点跳过但是不要直接标记访问，因为可能之后的点会用到之前的坏点标记自身。
然而因为数据范围有问题wa了好多次。。。
于是看了题解：
大概都是另一种做法（而且都加入了输入挂，不懂，怎么感觉这些人是互相抄的2333）
从最高的点开始做dfs，每次把不大于当前点高度的点都访问掉。。。算作一次访问。
访问次数就是答案。
想了下确实比较巧妙，比较好写，然而比我的写法要慢。
然而窝不懂为什么这种写法数组开小就是返回RE,而我的写法数组开销就是返回WA…
我的做法（800ms,bfs）：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月03日 星期日 20时01分12秒
4File Name :code/bzoj/1619.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int dx8[8]={1,1,1,0,0,-1,-1,-1};
33const int dy8[8]={1,0,-1,-1,1,1,0,-1};
34const int inf = 0x3f3f3f3f;
35const int N=705;
36int h[N][N];
37bool bad[N][N];
38int n,m;
39bool vis[N][N];
40void checkvis();
41
42struct node
43{
44 int x,y;
45
46 bool inmaze ()
47 {
48 if (x>=1&&y>=1&&x<=n&&y<=m) return true;
49 return false;
50 }
51
52 void look()
53 {
54 cout<<x<<" "<<y<<endl;
55 }
56}s;
57bool ok ( int x,int y)
58{
59 // if (x-1>=1&&h[x-1][y]>h[x][y]) return false;
60 // if (x+1<=n&&h[x+1][y]>h[x][y]) return false;
61 // if (y-1>=1&&h[x][y-1]>h[x][y]) return false;
62 // if (y+1<=m&&h[x][y+1]>h[x][y]) return false;
63
64 for ( int i = 0 ; i < 8 ; i++)
65 {
66 int nx = x + dx8[i];
67 int ny = y + dy8[i];
68 if (nx<1||nx>n||ny<1||ny>m) continue;
69 if (h[nx][ny]>h[x][y]) return false;
70 }
71 return true;
72}
73
74
75bool bfs( int x,int y)
76{
77 queue<node>q;
78 s.x = x;
79 s.y = y;
80 q.push(s);
81 vis[x][y] = true;
82 bool res = true;
83 while (!q.empty())
84 {
85 node pre = q.front() ;q.pop();
86// pre.look();
87// checkvis();
88 if (!res) bad[pre.x][pre.y] = true;
89
90
91 for ( int i = 0 ; i < 8 ; i++)
92 {
93 node nxt;
94 nxt.x = pre.x + dx8[i];
95 nxt.y = pre.y + dy8[i];
96 if (!nxt.inmaze()) continue;
97 if (vis[nxt.x][nxt.y]) continue;
98 // vis[nxt.x][nxt.y] = true;
99 if (h[nxt.x][nxt.y]!=h[pre.x][pre.y]) continue;
100 if (bad[nxt.x][nxt.y])
101 {
102 res = false;
103 }
104 if (!ok(nxt.x,nxt.y))
105 {
106 res = false;
107 }
108// nxt.look();
109 q.push(nxt);
110 vis[nxt.x][nxt.y] = true;
111 }
112 }
113
114 return res;
115
116}
117
118void checkbad()
119{
120 for ( int i = 1 ; i <= n ; i++)
121 {
122 for ( int j = 1 ; j <= m ; j++)
123 {
124 cout<<bad[i][j]<<" ";
125 }
126 cout<<endl;
127 }
128}
129
130void checkvis()
131{
132 for ( int i = 1 ; i <= n ; i++)
133 {
134 for ( int j = 1 ; j <= m ; j++)
135 {
136 cout<<vis[i][j]<<" ";
137 }
138 cout<<endl;
139 }
140}
141int main()
142{
143 #ifndef ONLINE_JUDGE
144 freopen("code/in.txt","r",stdin);
145 #endif
146
147 ios::sync_with_stdio(false);
148 cin>>n>>m;
149 for ( int i = 1 ; i <= n ; i++)
150 for ( int j = 1 ; j <= m ; j++) cin>>h[i][j];
151 ms(bad,false);
152
153 for ( int i = 1 ; i <= n ; i++)
154 {
155 for ( int j = 1 ; j <= m ; j++)
156 {
157 if (!ok(i,j)) bad[i][j] = true;
158 }
159 }
160 ms(vis,false);
161// checkbad();
162 int ans = 0 ;
163 for ( int i = 1 ; i <= n ; i++)
164 {
165 for ( int j = 1 ; j <= m ; j++)
166 {
167 if (vis[i][j]) continue;
168 if (bad[i][j]) continue;
169 if (bfs(i,j))
170 {
171 ans++;
172 // cout<<i<<" "<<j<<endl;
173 }
174 // else cout<<"bad:"<<endl;
175 }
176 }
177
178 cout<<ans<<endl;
179
180
181
182 #ifndef ONLINE_JUDGE
183 fclose(stdin);
184 #endif
185 return 0;
186}
网上题解的做法（940ms,dfs）：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月03日 星期日 21时33分17秒
4File Name :code/bzoj/r1619.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#include <assert.h>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int dx8[8]={1,1,1,0,0,-1,-1,-1};
34const int dy8[8]={-1,0,1,1,-1,-1,0,1};
35const int inf = 0x3f3f3f3f;
36const int N=705;
37int n,m;
38bool vis[N][N];
39int he[N][N];
40
41struct node
42{
43 int x,y;
44 int val;
45
46 bool operator < (node b)const
47 {
48 return val>b.val;
49 }
50}h[N*N];
51
52inline int read()
53{
54 int x=0,f=1;char ch=getchar();
55 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
56 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
57 return x*f;
58}
59void dfs ( int x,int y)
60{
61 vis[x][y] = true;
62 for ( int i = 0 ; i < 8 ; i++)
63 {
64 int nx = x + dx8[i];
65 int ny = y + dy8[i];
66
67 if (nx<1||ny<1||nx>n||ny>m) continue;
68 if (he[x][y]<he[nx][ny]) continue;
69 if (vis[nx][ny]) continue;
70 dfs(nx,ny);
71 }
72}
73int main()
74{
75 #ifndef ONLINE_JUDGE
76 freopen("code/in.txt","r",stdin);
77 #endif
78
79 cin>>n>>m;
80 int cnt = 0 ;
81 for ( int i = 1 ; i <= n ; i++)
82 for ( int j = 1 ; j <= m ; j++)
83 {
84 cin>>he[i][j];
85 cnt++;
86 h[cnt].x = i;
87 h[cnt].y = j;
88 h[cnt].val = he[i][j];
89 }
90
91 sort(h+1,h+cnt+1);
92 ms(vis,false);
93
94 int ans = 0 ;
95 for ( int i = 1 ; i <= cnt ; i++)
96 {
97 int x = h[i].x;
98 int y = h[i].y;
99 assert(x>=1&&x<N);
100 assert(y>=1&&y<N);
101 if (!vis[x][y])
102 {
103 dfs(x,y);
104 ans++;
105 }
106
107 }
108
109 cout<<ans<<endl;
110
111 #ifndef ONLINE_JUDGE
112 fclose(stdin);
113 #endif
114 return 0;
115}