C++(g++ 7.5.0) 解法, 执行用时: 538ms, 内存消耗: 16224K, 提交时间: 2023-04-30 18:41:52

#include<bits/stdc++.h>
#define int long long
using namespace std;
int visit[1010][1010];
int maps[1010][1010];
int dx[]={0,0,1,-1,-1,1,1,-1};
int dy[]={1,-1,0,0,1,-1,1,-1};
int p,v;
int n;
int res1=0,res2=0;
typedef pair<int,int>pi;
void bfs(int x,int y)
{
	queue<pi>que;
	que.push({x,y});
	visit[x][y]=1;
    while(!que.empty())
    {
    	pi top=que.front();
    	que.pop();
    	int px=top.first;
    	int py=top.second;
    	for(int i=0;i<8;i++)
    	{
		   int tx=px+dx[i];
		   int ty=py+dy[i];
		   if(tx<0||tx>=n||ty<0||ty>=n)continue;
		   if(maps[x][y]!=maps[tx][ty])
		   {
			  if(maps[x][y]<maps[tx][ty])
			  {
				p=1;
			  }
			  else v=1;
		   }
		   else if(!visit[tx][ty]&&maps[x][y]==maps[tx][ty])
		   {
		   	  que.push({tx,ty});
			  visit[tx][ty]=1;
		   }
		}
	}
}
signed main()
{
   cin>>n;
   for(int i=0;i<n;i++)
   {
   	for(int i1=0;i1<n;i1++)cin>>maps[i][i1];
   }
   for(int i=0;i<n;i++)
   {
   	for(int i1=0;i1<n;i1++)
   	   {
   	   	   if(visit[i][i1]==0)
   	   	    {
   	   	    	p=0;v=0;
   	   	        bfs(i,i1);
   	   	        if(p==v&&p==0) res1=res2=1;
   	   	        else if(p*v==1)continue;
   	   	        res1+=v;
   	   	        res2+=p;
			}
	   }
   }
   cout<<res1<<" "<<res2<<endl;
}

C++ 解法, 执行用时: 361ms, 内存消耗: 5292K, 提交时间: 2022-07-04 12:05:59

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}s,t;
int w[1001][1001],n,ans1,ans2;
bool v[1001][1001];
queue <node> q;
void bfs(const int &x,const int &y){
	s.x = x;
	s.y = y;
	q.push(s);
	v[x][y] = 1;
	int i,j;
	bool f1 = 0,f2 = 0;
	while (!q.empty()){
		t = q.front();
		q.pop();
		for (i = -1;i <= 1;i++)
			for (j = -1;j <= 1;j++){
				s.x = t.x + i;
				s.y = t.y + j;
				if (s.x < 1 || s.x > n || s.y < 1 || s.y > n)
					continue;
				if (w[s.x][s.y] > w[t.x][t.y])
					f1 = 1;
				else if (w[s.x][s.y] < w[t.x][t.y])
					f2 = 1;
				else if (!v[s.x][s.y]){
					q.push(s);
					v[s.x][s.y] = 1;
				}
			}
	}
	if (!f1 && f2)
		ans1++;
	else if (f1 && !f2)
		ans2++;
	else if (!f1){
		ans1++;
		ans2++;
	}
}
int main(){
	int i,j;
	cin>>n;
	for (i = 1;i <= n;i++)
		for (j = 1;j <= n;j++)
			cin>>w[i][j];
	for (i = 1;i <= n;i++)
		for (j = 1;j <= n;j++)
			if (!v[i][j])bfs(i,j);
	cout<<ans1<<' '<<ans2;
	return 0;
}