记录编号	286131	评测结果	AAAAAAAAAA
题目名称	[POI 2007] 山峰和山谷	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.295 s
提交时间	2016-07-26 20:04:28	内存使用	7.96 MiB

#include <fstream>
#include <queue>
#define  M 1001
using namespace std;
ifstream cin("grz.in");
ofstream cout("grz.out");
int e[M][M],book[M][M],now,n,ans_f,ans_g;
int t[9][3]={{0,0,0},{0,-1,0},{0,-1,1},{0,0,1},{0,1,1},{0,1,0},{0,1,-1},{0,0,-1},{0,-1,-1}};
int mn,mx;
class mon
{
public:
	int x,y;
	mon(int _x,int _y)
	{
		x=_x;
		y=_y;
	}
	mon (){}
};
queue <mon> q;
int bfs(int start_x,int start_y)
{
	mon a(start_x,start_y);
	
	q.push(a);
	
	
	book[start_x][start_y] =1;
	while (!q.empty())
	{
		
		mon h=q.front();
		q.pop();
	
		for(int k=1;k<=8;k++)
		{
			mon r(h.x+t[k][1],h.y+t[k][2]);
			if(r.x<1||r.x>n||r.y<1||r.y>n)
				continue;
				mx=max(mx,e[r.x][r.y]);
				mn=min(mn,e[r.x][r.y]);
				if(e[r.x][r.y]==now)
					if(book[r.x][r.y]==0)
				{
					book[r.x][r.y]=1111;
				
					q.push(r);
				}
			
		}
	}
	return 0;
}

int main()
{
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			cin>>e[i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(book[i][j]==0)
			{
				now=e[i][j];
				mn=mx=now;
				bfs(i,j);
				
				if(mn<=now&&mx<=now)
					ans_f++;
				if(mn>=now&&mx>=now)
					ans_g++;
			}
		}
	cout<<ans_f<<' '<<ans_g<<endl;
	cin.close();	
	cout.close();		
	return 0;
}