Guarding the Farm
Guarding the Farm
Time Limit: 1000 ms Memory Limit: 65536 KBTotal Submit: 23 Accepted: 18
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 ≤ 100) rows and M (1 < M ≤ 70) 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.
* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
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
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
int map[100][100];//用来储存山头；
int used[100][100];//用来标记是否被使用；
int X[8]={1,1,1,-1,-1,-1,0,0};
int Y[8]={1,-1,0,1,-1,0,1,-1};
int n,m;
int xx,yy;
void DFS(int x,int y){
used[x][y]=1;
// int xx,yy;
for(int i=0;i<8;i++)
for(int j=0;j<8;j++){
xx=X[i]+x;
yy=Y[i]+y;
if(xx>=0 && xx<n && yy>=0 && yy<m && !used[xx][yy] && map[xx][yy]<=map[x][y])
DFS(xx,yy);
}
map[x][y]=0;//此方法为暴力查找，每次找最高的山头……把不比它高的山头削去…… 在100X100的范围内可以
//保证AC…… 但此题如将数据强化到700X700时…… 暴力会TLE
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&map[i][j]);
int max,sum=0,px,py;
while(1){
max=0;//最高的山顶
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(max<map[i][j]){
max=map[i][j];px=i;py=j;//记录最高的位置
}
if(max>0){
sum++;//既然是最高…… 必然是山顶……
DFS(px,py);//开始削= =|||
}
else
break;//等于0必然没有山顶了= =
}
printf("%d\n",sum);
}
明天标注…… 累死了T_T^
…… 做了几天搜索= =…… 发现对BFS和DFS还有点了解…… DFS是深度优先，当它找到一条可行路时，就会一直往下走，直到找到目标。当找不到目标时，就返回上一次走的岔口。这就是回溯。BFS是宽度优先，它先找到与之临近的，即使这次搜索部分具有满足下一步行动的条件，它也不进行下一步搜索，而是等到第一次搜索全部结束时，才取出满足下一步行动的所有解，继续搜索，如此反复。（扫雷时触雷时雷的爆炸方式就是如此，也和石子扔入水中时产生的波纹一样。）这就造成了此种解法必然有最优解。所以在只求有解，不求最优时，DFS首当其冲，而具有最优解时，BFS应该先考虑…… 当然…… 类似于迷宫问题…… 应该用BFS，DFS会溢出…… 造成RE= =~……先写到这…… 今天一题未做…… T_T
其加强版…… 未注释…… = =…… 改天…… 判断条件的优化，搜索的策略不同…… 大大优化了速度…… 各位童鞋可以比较下二者的优异……
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
int map[800][800];
int used[800][800];
int d[8][2]={{1,0,},{1,-1},{1,1},{-1,0},{-1,1},{-1,-1},{0,1},{0,-1}};
bool ok;
int n,m,sum=0;
void DFS(int x,int y){
int xx,yy;
for(int i=0;i<8;i++){
xx=d[i][0]+x;
yy=d[i][1]+y;
if(xx>=0 && xx<n && yy>=0 && yy<m){
if(map[xx][yy]>map[x][y])
ok=0;
if(map[xx][yy]==map[x][y] && !used[xx][yy]){
used[xx][yy]=1;
DFS(xx,yy);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&map[i][j]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(!used[i][j] && map[i][j]){
ok=1;
DFS(i,j);
if(ok)
sum++;
}
printf("%d\n",sum);
}