大佬们,萌新求助,刚学OI一分钟
查看原帖
大佬们,萌新求助,刚学OI一分钟
278481
Link_Space楼主2020/8/7 10:57

找了很久都没找出哪里错了,求大佬指出

#include<iostream>
#include<queue>
using namespace std;
int mama[2000][2000];
typedef pair<int, int> PII;
int n;
int dx[8] = { 1,-1,0,0,1,-1,1,-1 };
int dy[8] = { 0,0,-1,1,-1,1,1,-1 };
int aim[2000][2000];
bool chan[2000][2000];
int highh;
int loww;
int bfs2(int x,int y)
{
	chan[x][y] = 1;
	queue<PII> q;
	q.push({ x,y });
	while (!q.empty())
	{
		PII temp = q.front();
		q.pop();
		int x1 = temp.first;
		int y1 = temp.second;
		for (int i = 0; i < 8; i++)
		{
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx<1 || xx>n || yy<1 || yy>n)
				continue;
			if (mama[xx][yy] == mama[x1][y1] && aim[xx][yy] == aim[x1][y1]&&!chan[xx][yy])
			{	
				chan[xx][yy] = 1;
				q.push({ xx, yy });
			}
			if (mama[xx][yy] == mama[x1][y1] && aim[xx][yy] != aim[x1][y1])
			{
				return 0;
			}
		}
	}
	return aim[x][y];
}
int main()
{
	bool is = true;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> mama[i][j];
			if (mama[i][j] != mama[i][j - 1] && j != 1)
				is = false;
		}
		if (mama[i][n] != mama[i - 1][n] && i != 1)
			is = false;
	}
	if (is)
	{
		cout << "1 1";
		return 0;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			bool isf=true;
			bool isg = true;
			for (int k = 0; k < 8; k++)
			{
				int xx = i + dx[k];
				int yy = j + dy[k];
				if (xx<1 || xx>n || yy<1 || yy>n)
					continue;
				if (mama[xx][yy] > mama[i][j])
					isf = false;
				else if (mama[xx][yy] < mama[i][j])
					isg = false;
			}
			if (isf && !isg)
				aim[i][j] = 1;
			else if (!isf && isg)
				aim[i][j] = 2;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (aim[i][j]&&!chan[i][j])
			{
				chan[i][j] = 1;
				int fu = bfs2(i, j);
				if (fu==2)
				{
					loww++;
				}
				else if (fu == 1)
				{
					highh++;
				}
			}
		}
	}
	cout << highh << " " << loww;
	return 0;
}
2020/8/7 10:57
加载中...