并查集做法 25pts求调(帮助必关
查看原帖
并查集做法 25pts求调(帮助必关
1473722
Q1021楼主2025/1/1 16:25
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int arr[1100][1100];
const int P = 0x3f3f3f3f;
int all[1100][1100];
int ans = 0;

int p[1100000];
int sz[1100000];

inline int find(int x)
{
	return p[x] == x ? x : x = find(p[x]);
}

inline void join(int x, int y)
{
	int px = find(x), py = find(y);
	if (px == py) return;
	sz[py] += sz[px];
	sz[px] = 0;
	p[px] = py;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	cin >> n >> m;
	for (int i = 0; i < 1100; i++)
	{
		for (int j = 0; j < 1100; j++)
		{
			arr[i][j] = all[i][j] = 99999;
		}
	}

	for (int i = 1; i <= n * m; i++)
	{
		p[i] = i;
		sz[i] = 1;
	}



	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1)
			{
				arr[i][j] = -1;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (arr[i][j] == -1)
			{
				all[i][j] = -1;
				continue;
			}
			int sum = 0;
			for (int k = i - 1; k <= i + 1; k++)
			{
				for (int h = j - 1; h <= j + 1; h++)
				{
					if (k == i && h == j)
					{
						continue;
					}
					else
					{
						if (arr[k][h] == -1)
						{
							sum++;
						}

					}
				}
			}
			all[i][j] = sum;

		}
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			
			if (all[i][j] == -1)
			{
			
				continue;
			}
			bool flag = 0;
			for (int k = i - 1; k <= i + 1; k++)
			{
				for (int h = j - 1; h <= j + 1; h++)
				{
					if (k == i && h == j)
					{
						continue;
					}
					else
					{
						if (all[k][h] == 0)
						{
							flag = 1;
							break;
							
						}

					}
				}
				if (flag == 1) break;
			}
			if (flag == 0)
			{
			//	cout << i << " " << j << endl;
				ans++;
			}
		
			

		}
		
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (all[i][j] != 0)
			{
				continue;
			}
			int x = i * m + j;
			bool flag = 0;
			for (int k = i - 1; k <= i + 1; k++)
			{
				for (int h = j - 1; h <= j + 1; h++)
				{
					if (k == i && h == j) continue;
					if (all[k][h] == 0)
					{
						flag = 1;
						int y = k * m + h;
						join(x, y);
					}
				}
			}
			if (flag == 0) ans++;

		}
	}



	for (int i = 1; i <= n * m; i++)
	{
		if (sz[i] > 1) ans++;
	}


	cout << ans;
	














	return 0;
}
2025/1/1 16:25
加载中...